Torre de Hanoi – Como funciona essa solução recursiva?

Torre de Hanoi – Como funciona essa solução recursiva?

6 de outubro de 2019 0 Por Ramos de Souza Janones
Powered by Rock Convert

Vamos brincar com o Python utilizando o problema da Torre de Hanói, o mais famoso em testes com esta poderosa linguagem de programaçã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.

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):

  1. resolva o problema para N – 1 discos, só que movendo de A para C (ou seja, usando C como destino e B como auxiliar)
  2. mova 1 disco de A para B (da origem para o destino)
  3. 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.

DEVE GOSTAR: Data Science do Zero 

Por exemplo, se eu tiver 5 discos e quiser movê-los de A para B (sendo C a torre auxiliar). A ideia é:

Leia também:  
Powered by Rock Convert
Como vender Software - Seja desktop, web ou MobilePowered by Rock Convert
  • 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')

A saída seria:

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.

VOCÊ ESTÁ EM: » Programação » Python

Powered by Rock Convert
Siga os bons!
Últimos posts por Ramos de Souza Janones (exibir todos)