O algoritmo da Torre de Hanói

procedure hanoi(n, source, target, spare)
    if n == 0 then
        return
    hanoi(n - 1, source, spare, target)
    move disk n from source to target
    hanoi(n - 1, spare, target, source)
end procedure

O que observar

• Os papéis giram. A torre B é a auxiliar da primeira chamada e o destino da chamada que ela faz. Cada nível de recursão reetiqueta as três torres, e esse reetiquetar é todo o truque.
• A pilha nunca fica funda. Três discos nunca têm mais de 4 chamadas rodando ao mesmo tempo — uma por número de discos, de 3 até 0 — mesmo que o programa faça 15 chamadas ao todo.
• Metade das chamadas não faz nada. Dessas 15 chamadas, 8 são de zero discos e retornam na hora. São o preço do caso base mais simples possível.
• A linha que move roda exatamente 2ⁿ − 1 vezes. Sete, para três discos, ao longo dos 43 passos da execução.

O primeiro é o mais difícil de pegar enquanto o programa roda, porque nada se mexe no tabuleiro quando acontece: só mudam os nomes embaixo das torres. Aqui ele está parado: a primeira chamada, as duas abaixo dela a caminho da jogada 1, e a chamada que traz a pilha de volta.

1. hanoi(3, A, C, B)

   A primeira chamada: mover os 3 discos de A para C. Isso deixa B como auxiliar. Origem A, destino C, auxiliar B.

2. hanoi(2, A, B, C)

   A primeira chamada dela. O disco 3 não pode se mover com os discos 1 e 2 em cima, e eles não podem ir para C, para onde o disco 3 está indo. Então B, que há pouco era a auxiliar, é o destino, e C é a auxiliar. Origem A, destino B, auxiliar C.

3. hanoi(1, A, C, B)

   Um nível abaixo, a mesma troca outra vez. Para liberar o disco 2, o disco 1 vai para C, e B volta a ser a auxiliar. Origem A, destino C, auxiliar B.

4. hanoi(2, B, C, A)

   O disco 3 já atravessou. A segunda chamada da raiz traz os discos 1 e 2 de volta de B para cima dele, então agora B é a origem e A, onde todos os discos começaram, é a auxiliar. Origem B, destino C, auxiliar A.

O segundo é mais fácil de duvidar do que de conferir, então aqui está a execução inteira com a altura da pilha em cada um de seus passos:

• A execução leva 43 passos e faz 15 chamadas ao todo.
• O número de chamadas na pilha sobe e desce entre 0 e 4, e chega a 4 em 8 desses passos — toda vez que uma chamada sem disco para mover começa e retorna.
• A profundidade 4 é n + 1 para n = 3, e nenhum passo da execução passa disso.

A árvore de recursão

Desenhe cada chamada como uma caixa sob a chamada que a fez e o programa vira uma árvore. Coloque cada caixa acima do número da jogada que ela faz e aparece outra coisa: ler as caixas da esquerda para a direita dá as jogadas em ordem. Com três discos, a jogada da própria primeira chamada — o maior disco — é a jogada 4, bem no meio, com a solução inteira de três jogadas para dois discos de cada lado.

1. Jogada 1: a chamada com n = 1, de A para C, move o disco 1.
2. Jogada 2: a chamada com n = 2, de A para B, move o disco 2, entre suas duas chamadas com n = 1.
3. Jogada 3: a chamada com n = 1, de C para B, move o disco 1.
4. Jogada 4: a chamada com n = 3, de A para C, move o disco 3, entre suas duas chamadas com n = 2.
5. Jogada 5: a chamada com n = 1, de B para A, move o disco 1.
6. Jogada 6: a chamada com n = 2, de B para C, move o disco 2, entre suas duas chamadas com n = 1.
7. Jogada 7: a chamada com n = 1, de A para C, move o disco 1.

Essa simetria vale em qualquer tamanho. A jogada 2ⁿ⁻¹ é sempre o maior disco atravessando, e as jogadas antes e depois são a solução de (n − 1) discos jogada duas vezes, com duas torres trocando de papel. É por isso que uma lista de jogadas de qualquer tamanho se lê de relance, e por isso a solução de cinco discos é a de quatro, uma jogada, e a de quatro de novo.

Por que está correto

O algoritmo nunca quebra uma regra e sempre termina, e a demonstração é curta o bastante para ser dada por inteiro. A afirmação, para todo n, é:

Se os n discos do topo da torre de origem são os discos 1 a n, e todo disco em qualquer outro lugar é maior que n, então hanoi(n, source, target, spare) move esses n discos para o destino, de forma válida, e não toca em mais nada.

Para n = 0 não há nada para mover e nada é tocado.

Suponha que a afirmação vale para n − 1. Então cada um dos três passos é válido:

1. A primeira chamada move os discos 1 a n − 1 para a auxiliar. Ela tem esse direito: qualquer outro disco, inclusive o disco n, é maior que n − 1.
2. O disco n vai para o destino. Agora não há nada em cima dele, e o destino só tem discos maiores que n.
3. A segunda chamada move os discos 1 a n − 1 da auxiliar para o destino. Válida pelo mesmo motivo: o disco n, agora embaixo deles, é maior.

Todos os n discos estão no destino e nada mais se moveu. Por indução, a afirmação vale para todo n, e o quebra-cabeça completo é o caso em que a origem tem todos os discos.

1. Supostoa afirmação para n − 1

   A hipótese diz que uma chamada sobre n − 1 discos os move para onde mandarem, de forma válida, e não toca em mais nada. Aplicada aqui, ela leva os discos 1 a n − 1 da origem para a auxiliar. Ela tem esse direito: qualquer disco em que pudesse pousá-los — inclusive o disco n — é maior que qualquer um dos que está carregando.

2. Provado aquiuma jogada válida

   Este é o único passo que a demonstração precisa defender sozinha, e é uma única jogada. O disco n está livre, porque o passo anterior o liberou. O destino não contém nada além de discos maiores que n, porque tudo o que é menor está na auxiliar. Então a jogada é válida.

3. Supostoa afirmação para n − 1, de novo

   A mesma hipótese, usada uma segunda vez, traz os discos 1 a n − 1 da auxiliar para o destino. Válida pelo mesmo motivo de antes: o disco n, agora embaixo deles, é maior. Todos os n discos estão no destino e nada mais se moveu — que é a afirmação para n.

A recorrência, resolvida direito

Seja T(n) o número de jogadas que o algoritmo faz para n discos. A função faz duas chamadas sobre n − 1 discos e uma jogada própria, e não faz jogada alguma quando não há discos:

Para resolvê-la, substitua a recorrência nela mesma e procure o padrão. Isso se chama desenrolar, ou telescopar:

Enxergar um padrão não é prová-lo, então confirme por indução. T(0) = 0 = 2⁰ − 1. E se T(n − 1) = 2ⁿ⁻¹ − 1, então T(n) = 2(2ⁿ⁻¹ − 1) + 1 = 2ⁿ − 2 + 1 = 2ⁿ − 1. A forma fechada é exata para todo n.

Há um terceiro caminho, e ele é uma imagem que você já viu. A árvore de recursão acima é uma árvore binária completa: a raiz move n discos, as duas chamadas abaixo dela movem n − 1 cada, as quatro abaixo dessas movem n − 2, e assim por diante. A profundidade k tem, portanto, 2ᵏ chamadas, o último nível é a profundidade n − 1, e cada uma dessas chamadas faz exatamente uma jogada. Some os níveis e a conta sai como uma série geométrica:

Três métodos — desenrolar, indução e a árvore — e uma resposta só. Vale conhecer, porque existe um quarto que é oferecido o tempo todo e está errado.

A mesma aritmética conta as chamadas. Toda chamada com n {">"} 0 discos faz mais duas, então há C(n) = 2C(n − 1) + 1 chamadas com C(0) = 1, o que desenrola para 2ⁿ⁺¹ − 1. São 2ⁿ − 1 chamadas que movem um disco, mais 2ⁿ que retornam na hora.

Custo de tempo e de memória

Cada chamada faz uma quantidade constante de trabalho além das suas duas chamadas recursivas, então o tempo de execução é proporcional ao número de chamadas: Θ(2ⁿ). Nenhum algoritmo mais esperto consegue superar isso, porque a própria saída tem 2ⁿ − 1 jogadas de comprimento — e 2ⁿ − 1 é um mínimo comprovado, não apenas o melhor que alguém encontrou. A prova de que nenhuma solução é mais curta tem página própria: por que o mínimo é 2ⁿ − 1.

A memória é outra história. As chamadas não existem todas ao mesmo tempo: uma chamada termina antes de a irmã começar, então a pilha guarda apenas uma chamada por nível, de n até 0. O espaço usado é Θ(n) — sessenta e cinco quadros de pilha para os sessenta e quatro discos da lenda, o que qualquer computador segura sem perceber. O que acaba é o tempo: 18.446.744.073.709.551.615 jogadas a um bilhão por segundo ainda são 584 anos.

Esse número é o da lenda, e a lenda é mais nova do que parece. Um templo onde sacerdotes movem sessenta e quatro discos de ouro, e o mundo acabando quando terminarem, aparece impresso pela primeira vez em 1884 — num artigo que anunciava um quebra-cabeça posto à venda em Paris no ano anterior, sob o nome de um professor que não existia. No ritmo dos monges, uma jogada por segundo, restam ao mundo 585 bilhões de anos, cerca de quarenta vezes a idade atual do universo. O matemático por trás do quebra-cabeça e da história foi Édouard Lucas, que provou à mão que 2¹²⁷ − 1 é primo e morreu aos 49 anos de uma infecção causada por um corte de um prato que um garçom deixou cair num banquete.

Ponha números nessas fórmulas e os dois tipos de custo se separam. Cada disco a mais faz um pouco mais do que dobrar as jogadas e as chamadas, e acrescenta um único quadro à maior profundidade que a pilha alcança:

A calculadora de jogadas mínimas calcula as jogadas e o tempo para qualquer número de discos, e a última linha — o tamanho da lenda — tem uma página só dela.

Sem recursão

As mesmas jogadas podem ser produzidas por um laço simples com duas regras:

• Jogadas ímpares: o menor disco avança uma torre num circuito fixo — A → C → B para um número ímpar de discos, A → B → C para um número par.
• Jogadas pares: faça a única jogada válida que não envolve o menor disco. Sempre existe exatamente uma.

Essas duas regras reproduzem a solução recursiva jogada a jogada; a página da solução iterativa mostra por quê, e a joga em um tabuleiro.

Há uma versão ainda mais estranha, que não guarda torre nenhuma: o disco, a origem e o destino da jogada m podem ser lidos nos dígitos binários de m. Essa ligação, e o código de Gray escondido dentro dela, estão em Torre de Hanói, binário e código de Gray.

A partir de uma posição que não é o começo

A função dos livros pressupõe que todos os discos começam na torre de origem. Dê a ela um quebra-cabeça pela metade e ela não tem nada a dizer. Mais um caso resolve isso. Olhe para o maior disco:

• Já está na torre que ele precisa alcançar? Ele não precisa de jogada nenhuma. Resolva os discos menores mandando-os para essa mesma torre.
• Está em outro lugar? Tire os discos menores para a torre que não é nem onde ele está nem para onde ele vai, mova-o e siga como antes.

Essa versão encontra a solução mais curta a partir de qualquer posição válida, e é ela que o solucionador da Torre de Hanói executa.

Teste você mesmo

Três perguntas que a página já respondeu. Resolva-as antes de abrir — se alguma não sair, a seção citada junto com a resposta é a que vale reler.

1. Três discos são sete jogadas. Quantas são 5 discos, e quantas delas movem o próprio disco 5?

   Ver a resposta

   31 jogadas, que é 2⁵ − 1 — e exatamente uma delas move o maior disco. Todos os discos, menos o maior, se movem mais de uma vez, porque cada uma das duas metades da solução tem de movê-los. A recorrência, resolvida direito.

2. hanoi(3, A, C, B) faz hanoi(2, A, B, C) como primeira chamada. Por que o destino dessa chamada é B e não C?

   Ver a resposta

   Porque o disco 3 vai para C, e só pode pousar lá se C estiver vazia. Então os dois discos acima dele têm de ficar estacionados em outro lugar, e esse outro lugar só pode ser B. A torre que uma chamada mira vira a torre que a primeira chamada dela precisa manter livre — e é por isso que dois dos três argumentos trocam de lugar na entrada. O que observar.

3. Resolver 20 discos faz 2.097.151 chamadas. Quantas delas estão na pilha no mesmo instante, no máximo?

   Ver a resposta

   21 — uma por número de discos, de 20 até 0. Uma chamada termina antes de a irmã começar, então as chamadas nunca existem todas ao mesmo tempo: o trabalho é exponencial e a memória é linear. Custo de tempo e de memória.

O algoritmo na sua linguagem

A mesma função em seis linguagens, cada uma com um programa que roda, uma explicação linha a linha, o tabuleiro rodando ao lado e o que é específico daquela linguagem — o que passa a importar assim que você tenta contar as jogadas de sessenta e quatro discos. Essas seis páginas estão em inglês.

• Torre de Hanói em PythonENRecursive and iterative programs, why Python's recursion limit never bites here, and integers that simply do not overflow.
• Torre de Hanói em JavaScriptENWhy 2 ** 64 − 1 prints the wrong number, BigInt, and a generator that hands out one move at a time.
• Torre de Hanói em JavaENWhy (1L << 64) − 1 is zero, counting with BigInteger, and the same solution driven by an explicit stack.
• Torre de Hanói em CENUndefined shifts, uint64_t, and a loop that reads every move straight off the bits of the move number.
• Torre de Hanói em C++ENCollecting the moves in a std::vector, the 64-disk count checked by the compiler, and three pairs of towers in a loop.
• Torre de Hanói em C#ENTop-level statements, an iterator whose moves LINQ can query, and ulong, checked arithmetic and UInt128 for the move count.

As palavras desta página

Caso base

A versão do problema que uma função recursiva responde de imediato, sem chamar a si mesma. É o que faz a recursão parar. Aqui é n = 0: nenhum disco para mover, então não há nada a fazer e a chamada retorna. Toda cadeia de chamadas, por mais funda que seja, termina em um deles.

Caso recursivo

Tudo o que não é o caso base: a parte da função que resolve uma versão menor do mesmo problema e constrói a resposta a partir dela. Aqui são as três linhas que tiram n − 1 discos do caminho, movem o disco n e trazem os n − 1 de volta.

Pilha de chamadas

A lista de chamadas de função que começaram e ainda não terminaram, a mais recente por último. Uma chamada entra quando começa e sai quando retorna, então a pilha é como um programa lembra para onde voltar. É o que o painel acima desenha, e é memória de verdade — por isso a profundidade dela é o custo de espaço do algoritmo.

Quadro de pilha

Uma entrada da pilha de chamadas: os argumentos e as variáveis locais de uma única chamada. Cada linha da pilha no painel é um quadro, com o n daquela chamada e a ideia própria dela de qual torre é a origem, o destino e a auxiliar. Sessenta e quatro discos precisam de sessenta e cinco quadros, o que não é nada; o problema são as jogadas.

Telescopar

Também chamado de desenrolar: resolver uma recorrência substituindo-a nela mesma até o padrão ficar óbvio, e então fixar o número de substituições para que só reste o valor inicial conhecido. Chama-se telescopar porque os termos do meio se encaixam como as seções de uma luneta.

Θsaid “theta maiúsculo”

Uma taxa de crescimento que é ao mesmo tempo limite superior e inferior: Θ(2ⁿ) quer dizer que o custo cresce como 2ⁿ, e não apenas que não cresce mais rápido que isso. O(2ⁿ) prometeria só o teto. Θ é a notação honesta aqui, porque este algoritmo realmente faz 2ⁿ − 1 jogadas — ele não tem como dar sorte e terminar antes.

Perguntas frequentes

Como funciona o algoritmo recursivo da Torre de Hanói?

Para mover n discos de uma torre de origem para uma torre de destino, ele primeiro move os n − 1 discos de cima para a torre auxiliar, depois move o maior disco para o destino, e depois move os n − 1 discos da auxiliar para o destino. Cada uma dessas duas transferências menores é o mesmo problema com um disco a menos, então a função chama a si mesma para elas, e uma chamada sem disco para mover simplesmente retorna.

A Torre de Hanói é dividir para conquistar ou programação dinâmica?

É dividir para conquistar. O problema é dividido em dois subproblemas de n − 1 discos, cada um é conquistado por recursão, e o passo de combinação é uma única jogada do maior disco. Não é programação dinâmica, e memoização não ajuda — mesmo que os subproblemas de fato se repitam. Com três torres só há seis maneiras de nomear origem, destino e auxiliar, então hanoi(1, A, C, B) é realmente chamada duas vezes ao resolver três discos. Guardar isso em cache não rende nada, porque a resposta de um subproblema é uma lista de 2ᵏ − 1 jogadas, e repetir uma lista guardada desse tamanho custa o mesmo que produzi-la. Aqui o trabalho é a saída, e nenhuma tabela deixa a saída mais curta.

O Teorema Mestre se aplica à recorrência da Torre de Hanói?

Não. O Teorema Mestre cobre recorrências da forma T(n) = aT(n/b) + f(n), em que cada subproblema é uma fração do original. A recorrência da Torre de Hanói é T(n) = 2T(n − 1) + 1: o subproblema é um disco menor, não uma fração do tamanho. Desenrolá-la dá T(n) = 2ⁿ − 1 direto, e a indução confirma.

Até que profundidade vai a recursão?

Com caso base em n = 0, há no máximo n + 1 chamadas na pilha ao mesmo tempo: uma por número de discos, de n até 0. Com caso base em n = 1, são n. De um jeito ou de outro a profundidade cresce linearmente, e é por isso que a solução recursiva precisa de apenas O(n) de memória mesmo fazendo um número exponencial de jogadas.

Quantas chamadas de função a solução recursiva faz?

2ⁿ⁺¹ − 1 chamadas quando o caso base é n = 0: as 2ⁿ − 1 chamadas que movem um disco, mais 2ⁿ chamadas que não encontram nada para mover e retornam. Três discos fazem 15 chamadas. Escrito com caso base em n = 1, o mesmo programa faz exatamente 2ⁿ − 1 chamadas, uma por jogada.

O algoritmo iterativo é mais rápido que o recursivo?

Não de um jeito que importe. Os dois precisam produzir 2ⁿ − 1 jogadas, então os dois levam tempo proporcional a 2ⁿ. A versão iterativa evita o custo das chamadas de função e não tem como estourar a pilha, mas a recursão aqui tem só n níveis de profundidade: estourar a pilha não é risco real para nenhum número de discos que você pudesse esperar.

Como é o algoritmo da Torre de Hanói em um fluxograma?

Não fica grande coisa, e essa é a resposta honesta. Um fluxograma mostra o controle passando por caixas uma vez, e a segunda caixa deste algoritmo é o fluxograma inteiro de novo — três níveis abaixo, com duas torres trocadas e um disco a menos. Um fluxograma não tem notação para isso, então um fluxograma da solução recursiva ou está errado, ou é a figura de uma única chamada com duas caixas escritas “chamar hanoi”, o que não ensina nada além do que o pseudocódigo de quatro linhas ensina. O diagrama que expressa isso é a árvore de recursão: cada chamada desenhada sob a chamada que a fez, com cada caixa acima da jogada que ela faz. Ela está nesta página, e ler as caixas da esquerda para a direita dá as jogadas em ordem.

O algoritmo consegue resolver um quebra-cabeça já pela metade?

A versão dos livros não: ela pressupõe que todos os discos começam em uma torre. Ela se generaliza com um caso a mais — se o maior disco já está no destino dele, pule-o e resolva os discos acima — e essa versão encontra a solução mais curta a partir de qualquer posição válida. O solucionador deste site executa exatamente isso. Abrir o solucionador →