9

Alguém poderia me explicar a lógica desta função recursiva? Não estou conseguindo entender do if para baixo. O código resolve o problema da Torre de Hanoi:

def toweOFhanoi(disc,ori,dest,aux):
    if disc == 1:
        print('Move disc {} from tower {} to the tower{}'.format(disc,ori,dest))
        return

    toweOFhanoi(disc - 1,ori,aux,dest)
    print('Move disc {} from tower {} to the tower {}'.format(disc,ori,dest))
    toweOFhanoi(disc - 1,aux,ori,dest)
    print('Move disc {} from tower {} to the tower {}'.format(disc,ori,dest))
3
  • 1
    python-course.eu/towers_of_hanoi.php Commented 25/09/2019 às 18:19
  • Pelo que entendi você quer saber como funciona certo? Se sim a função em questão ela esta comparando a possibilidade de movimentação seja ela na torre ou para a torre. Se não for isso por favor reformule a pergunta. Commented 25/09/2019 às 18:25
  • 3
    "Não estou conseguindo entender do if para baixo". Mais fácil você falar que não entendeu nada... hahaha Commented 25/09/2019 às 20:14

3 Respostas 3

10

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

  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.

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

3
  • 2
    Ahhh bem que eu achei estranho o segundo print e nem testei :(
    – Woss
    Commented 25/09/2019 às 19:03
  • Mals galera, lógica em aprimoramento hauah Me ajudou muito, obrigado!!!
    – Carlos
    Commented 25/09/2019 às 19:43
  • @Carlos É normal ter dificuldade com recursão, a primeira vez que vi achei que era bruxaria e demorei muito pra entender. Outra coisa: se uma das respostas resolveu o seu problema, vc pode escolher a que melhor resolveu e aceitá-la, veja aqui como e porque fazê-lo. Não é obrigatório, mas é uma boa prática do site, para indicar a futuros visitantes que aquilo resolveu o problema. E quando tiver 15 pontos, vc também poderá votar em todas as respostas que achou úteis.
    – hkotsubo
    Commented 25/09/2019 às 20:03
8

Esse é um caso que para você entender como foi desenvolvido a função para resolver a torre de Hanoi você precisa considerar que já existe uma função para resolver a torre de Hanoi. Confuso? Não, recursivo.

inserir a descrição da imagem aqui

Vamos considerar que nosso objetivo é passar os discos de A para C, sendo B nosso auxiliar. Para que o resultado seja válido, o disco 3 deve ser o primeiro em C, correto? Para movermos o disco 3 para C precisaremos mover primeiro os discos 1 e 2 para B.

O problema de mover os discos 1 e 2 para B também é uma torre de Hanoi, mas agora de 2 discos:

inserir a descrição da imagem aqui

E nesse caso a torre C será nossa auxiliar. Lembra que eu disse no início que você precisa considerar que já existe uma função que resolve a torre de Hanoi? Então, chamamos ela para resolver a torre com 2 discos e teremos:

inserir a descrição da imagem aqui

Agora basta mover o disco 3 para C.

inserir a descrição da imagem aqui

Para mover os discos 1 e 2 para C teremos outra torre de Hanoi com 2 discos para resolver, agora com a origem em B, destino em C, com a torre A como auxiliar. Por sorte já temos uma função que resolve isso.

Feito isso, teremos a torre completamente resolvida.

inserir a descrição da imagem aqui

Ou seja, para resolver a torre para 3 discos, mudando de A para C, com B auxiliar, fizemos:

  1. Resolvemos a torre de Hanoi com 2 discos de A para B, com C auxiliar;
  2. Movemos o disco 3 de A para C;
  3. Resolvemos a torre de Hanoi com 2 discos de B para C, com A auxiliar;

Correto? Agora reveja o código (simplificado):

def tower_of_hanoi(disc, orig, dest, aux):

    # 1. Resolve a torre de Hanoi para n-1 discos, movendo para o disco auxiliar:
    tower_of_hanoi(disc-1, orig, aux, dest)

    # 2. Move o maior disco para a torre destino:
    print('Move disc {} from tower {} to the tower {}'.format(disc, orig, dest))

    # 3. Resolve a torre de Hanoi para n-1 discos, movendo da torre auxiliar para a destino:
    tower_of_hanoi(disc - 1, aux, ori, dest)

Pronto, a mágica foi feita.

Mas aí você pensa: "Ok, mas como resolver a torre de Hanoi para 2 discos?". Simples, é a mesma lógica (por isso é recursivo). Quando for resolver a torre para 2 discos você antes resolve para 1 disco (n-1), porém, quando você possui apenas 1 disco não tem muito segredo, você pode movê-lo livremente. Com isso criamos a nossa condição de parada da recursividade: se a torre possuir apenas 1 disco, move-o e finaliza a função.

Isso é implementado pelo if:

# Se possuir apenas 1 disco:
if disc == 1:
    # Move o disco e finaliza a função
    print('Move disc {} from tower {} to the tower{}'.format(disc, ori, dest))
    return

Então, assim, para resolver uma torre de 3 discos ele precisa saber resolver uma de 2 discos; para resolver a de 2 discos precisa saber resolver uma de 1 disco; ele sabe resolver de 1 disco. Isso funcionará para qualquer quantidade de discos e três torres.

Veja Determinar o n-ésimo termo de Fibonacci com recursividade para mais informações de como funciona a recursividade.

3
  • 3
    Para entender recursão, antes vc precisa entender recursão... Eu ia desenhar as torres em ASCII mas fiquei com preguiça, +1 :-)
    – hkotsubo
    Commented 25/09/2019 às 19:08
  • Muito boa explicação, pensando desse jeito fica mais fácil de entender a lógica. Vlw msm!!!
    – Carlos
    Commented 25/09/2019 às 19:33
  • 1
    Boa resposta e com direito a ASCII Art. Commented 25/09/2019 às 21:22
2

Uma boa forma de entender como funciona métodos recursivos é entender o padrão dele.
(Facilita bem mais se você pegar a fórmula diretamente, mas enfim)

(Recursividade faz parte de um módulo de exatas: Análise matemática)

Primeiro precisamos achar o padrão.

Para mover n disco(s) quantos movimentos são necessários?
disco 1=1 movimento
disco 2=2 movimentos
disco 3=4 movimentos
total de movimentos para 3 discos? 7
total de movimentos para 2 discos? 3
total de movimentos para 1 disco? 1

Então podemos simplificar como notação científica (f(x)=2**x - 1) para sabermos quantos movimentos são necessários para completar o puzzle com X discos.

Mas e agora? Como iremos tornar essa função recursiva?

Se a = {1, 3, 7} então como faz para ter a2 a partir do a1? Simples! a2=2*a1+1

Então chegamos a formula do método!
inserir a descrição da imagem aqui

E por final, como carambolas funciona este método?

def recursivo(n, aux=0):
        if n == 0:
            return aux
        aux+=metodo(n-1, 1)
        aux+=metodo(n-1)
        return aux

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .