Primeiro, a função está errada, tem um print
a mais e a segunda chamada recursiva trocou a ordem das torres:
def hanoi(disc, ori, dest, aux):
if disc == 1:
print('Move disc {} from tower {} to the tower {}'.format(disc, ori, dest))
return
hanoi(disc - 1, ori, aux, dest)
print('Move disc {} from tower {} to the tower {}'.format(disc, ori, dest))
hanoi(disc - 1, aux, dest, ori)
Agora, ao problema. O problema da Torre de Hanói consiste em mover uma quantidade de discos de uma torre para outra (sendo que há uma terceira torre auxiliar). Os discos têm tamanhos diferentes, e um disco nunca pode ser colocado em cima de outro menor que ele. Além disso, só um disco pode ser movido por vez.
O if
trata do caso mais básico: quando há apenas 1 disco. Nesse caso a solução é fácil: mova o disco da torre inicial para a final, ou seja, da origem (ori
) para o destino (dest
).
Mas e se tivermos mais de um disco? Nesse caso, supondo que as torres são A (origem), B (destino) e C (auxiliar), a ideia do algorimo é (para N discos):
- resolva o problema para N - 1 discos, só que movendo de A para C (ou seja, usando C como destino e B como auxiliar)
- mova 1 disco de A para B (da origem para o destino)
- resolva o problema para N - 1 discos, só que movendo de C para B (ou seja, C é a origem, B é o destino e A é o auxiliar)
É isso que as chamadas recursivas estão fazendo. hanoi(disc - 1, ori, aux, dest)
corresponde ao passo 1 acima. O print
logo em seguida é o passo 2, e hanoi(disc - 1, aux, dest, ori)
é o passo 3.
O grande truque é que cada uma dessas chamadas recursivas pode gerar outras chamadas recursivas, até chegarem no caso em que só tem um 1 disco, que é quando elas retornam e voltam imprimindo os respectivos passos.
Por exemplo, se eu tiver 5 discos e quiser movê-los de A para B (sendo C a torre auxiliar). A ideia é:
- mover 4 discos da origem (A) para o auxiliar (C)
- mover o disco 5 para o destino (B)
- mover os 4 discos que estão no auxiliar (C) para o destino (B)
Mas como fazer o primeiro passo (mover 4 discos de A para C)? Simples, eu chamo a função novamente para 4 discos (N - 1), só que considerando que C é o destino e B é o auxiliar. Então ela fará todos os três passos acima, mas considerando esse novo contexto (4 discos, destino é C e B é auxiliar). A mesma coisa para o terceiro passo (só que agora são 4 discos cuja origem é C, destino é B e o auxiliar é A).
Por exemplo, se eu tiver 3 discos, a execução fica assim:
- primeiro eu resolvo o problema para 2 discos, movendo de A para C, usando B como auxiliar
- resolvo para 1 disco, movendo de A para B, usando C como auxiliar
- movo 2 de A para C
- resolvo para 1 disco, movendo de B para C, usando A como auxiliar
- movo o disco 3 de A para B
- resolvo para 2 discos, movendo de C para B, usando A como auxiliar
- resolvo para 1 disco, movendo de C para A, usando B como auxiliar
- movo 2 de C para B
- resolvo para 1 disco, movendo de A para B, usando C como auxiliar
Chamando no código, ficaria:
hanoi(3, 'A', 'B', 'C')
Saída:
Move disc 1 from tower A to the tower B
Move disc 2 from tower A to the tower C
Move disc 1 from tower B to the tower C
Move disc 3 from tower A to the tower B
Move disc 1 from tower C to the tower A
Move disc 2 from tower C to the tower B
Move disc 1 from tower A to the tower B
Veja o código rodando no IdeOne.com
O que pode confundir é que a cada chamada recursiva, as torres usadas como origem, destino e auxiliar mudam. Mas a lógica é a mesma para as chamadas (mova N - 1 discos da origem para o auxiliar, mova 1 disco da origem para o destino, mova N - 1 discos do auxiliar para o destino).
Lembrando ainda que para N discos, a solução requer 2N - 1 passos, e dependendo do N, essa quantidade toda de chamadas recursivas pode causar um estouro de pilha. A quantidade exata depende do valor do recursion limit (que pode ser alterado), mas o valor default não é tão grande assim (exemplo).
if
para baixo". Mais fácil você falar que não entendeu nada... hahaha