Quando se aprende “recursão” em programação, a Torre de Hanói quase sempre aparece. Resolvida à mão, leva centenas de movimentos, mas em um programa cabe em poucas linhas. Vamos ver como isso funciona, passo a passo. As hastes são esquerda, meio e direita, e os discos são numerados 1, 2, 3… do menor para o maior.

O que é recursão

Recursão é, dentro do método para resolver um problema, usar o mesmo método em um problema menor. Reduzindo cada vez mais, chega-se a um problema cuja resposta é imediata (com 0 discos, por exemplo, não se faz nada), e aí a recursão para.

Pensando na Torre de Hanói com recursão

Vamos pensar em mover uma torre de n discos da esquerda para a direita.

  1. Mova os n−1 discos de cima da esquerda para o meio.
  2. Mova o maior disco, o n, da esquerda para a direita.
  3. Mova os n−1 discos do meio para a direita.

Os passos 1 e 3 são o problema “mover uma torre de n−1 discos”, com a mesma forma do problema original. Só mudam as hastes de origem e de destino. Então, se criamos um único método “mover n discos de uma haste para outra, usando a haste restante”, ele pode chamar a si mesmo.

Pseudocódigo

método hanoi(n, origem, destino, auxiliar):
    se n for 0, não faz nada e termina
    hanoi(n − 1, origem, auxiliar, destino)    … tira os n−1 de cima
    mover o disco n da origem para o destino
    hanoi(n − 1, auxiliar, destino, origem)    … traz os n−1 de volta

hanoi(3, esquerda, direita, meio) gera a sequência para mover 3 discos da esquerda para a direita

Só com isso sai a sequência de movimentos mínima para qualquer quantidade de discos. Em Resolvendo a Torre de Hanói em Python e C há códigos que funcionam de verdade.

Como as chamadas se abrem

Escrevendo como hanoi é chamada com 3 discos, temos uma árvore como esta. Quanto mais recuada a linha, mais interna é a chamada.

hanoi(3, esquerda→direita)
├─ hanoi(2, esquerda→meio)
│   ├─ hanoi(1, esquerda→direita)     … 1 para a direita
│   ├─ 2 para o meio
│   └─ hanoi(1, direita→meio)         … 1 para o meio
├─ 3 para a direita
└─ hanoi(2, meio→direita)
    ├─ hanoi(1, meio→esquerda)        … 1 para a esquerda
    ├─ 2 para a direita
    └─ hanoi(1, esquerda→direita)     … 1 para a direita

Lendo de cima para baixo, a ordem dos “mover” é exatamente a resposta de 7 movimentos. Cada chamada gera duas chamadas internas, então, a cada disco a mais, o trabalho quase dobra.

Complexidade

O que se medeCom n discos
Número de movimentos2ⁿ−1
Número de chamadas de hanoi (contando as de 0 discos)2ⁿ⁺¹−1
Profundidade das chamadas (quanto é preciso guardar ao mesmo tempo)n+1 níveis

A razão de o número de movimentos ser 2ⁿ−1 está provada na fórmula do mínimo de movimentos. O tempo cresce de forma exponencial com o número de discos (O(2ⁿ)), e o que se guarda cresce só proporcionalmente (O(n)). Como são 2ⁿ−1 movimentos, por mais engenhoso que seja o método, escrever a sequência inteira leva todo esse tempo.

Solução sem recursão

Também dá para resolver só com repetição, sem recursão. É o próprio método de resolver à mão, apresentado no artigo sobre como resolver.

método hanoi_loop(n):
    definir o sentido do 1 (se n for ímpar: esquerda→direita→meio; se for par: esquerda→meio→direita)
    para movimento = 1, 2, 3, … , 2ⁿ − 1, repetir:
        se o movimento for ímpar, mover o disco 1 para a haste vizinha no sentido definido
        se o movimento for par, comparar os discos de cima das 2 hastes sem o 1
                       e mover o menor para o maior (ou para uma haste vazia)

Como não é preciso guardar as chamadas, como na recursão, a memória usada é muito pequena.

Com binário, achando direto qualquer movimento

Há também uma forma de achar o que fazer em qualquer movimento diretamente, sem percorrer os anteriores. Chame as hastes de 0, 1 e 2 e, para o movimento m (contado a partir de 1):

  • O disco a mover é o de número quantidade de zeros no final de m em binário + 1.
  • A haste de origem é o resto da divisão de (m AND (m − 1)) por 3.
  • A haste de destino é o resto da divisão de ((m OR (m − 1)) + 1) por 3.

AND e OR são os cálculos “e” e “ou” feitos bit a bit em binário. Por exemplo, para m = 4 (100 em binário), há 2 zeros no final, então o disco é o 3. A origem é (4 AND 3) = 0, a haste 0. O destino é ((4 OR 3) + 1) = 8, e o resto de 8 dividido por 3 dá a haste 2.

A sequência dada por essa fórmula move os discos da haste 0 para a haste 2 se há uma quantidade ímpar de discos, e da haste 0 para a haste 1 se há uma quantidade par. Para mover para a haste 2 com uma quantidade par, leia trocando as hastes 1 e 2. A relação entre o número de movimentos e o binário é explicada em detalhes no artigo sobre regularidades.