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.
- Mova os n−1 discos de cima da esquerda para o meio.
- Mova o maior disco, o n, da esquerda para a direita.
- 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 mede | Com n discos |
|---|---|
| Número de movimentos | 2ⁿ−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.
