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:  
Curso completo de Games, inclusive Realidade Aumentada.Powered 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

React Native Do Zero Ao Profissional: crie apps para Android e IOSPowered by Rock Convert
Siga os bons!

Ramos de Souza Janones

Janones, é um empreendedor brasileiro apaixonado por empreendedorismo e tecnologia. Ao longo dos anos trabalhando com o desenvolvimento de softwares desktop desde a linguagem Clipper, passando pelo Delphi e atualmente com Java.

Optou pela formação de Publicidade e Marketing por sua segunda empresa de tecnologia ter participado do "boom" da internet nos anos 90 e na procura de melhorar seus conhecimentos em negócios.

Em razão da principal formação e profundos conhecimentos em programação e banco de dados, é capaz de realizar o desenvolvimento de aplicativos web, desktop e mobile com maior criatividade e inovação que profissionais de desenvolvimento com uma formação única e mais especifica, dedicada somente ao desenvolvimento de softwares.

Com toda sua experiência com empresas de software, sua formação e paixão por negócios escreveu o livro "Marketing para Empresas e Profissionais de Software", publicado pela editora carioca Ciência Moderna em 2012. Além de outros livros sobre programação.




Frontend Do Zero Ao Profissional