Dúvida em Recursividade - Torres de Hanói

[ZNez]

Boas, estou aqui a ver uns exercícios na internet sobre recursividade e não estou a perceber muito em este. Será que alguém me pode explicar?

#-*-coding:cp1252-*-

def torres_hanoi(n,a,b,c):
"Implementação das torres de Hanói"
if n==1:
	print "move disco %d de %s para %s" % (n,a,c)
else:
	torres_hanoi(n-1,a,c,b)
	print "Move disco %d de %s para %s" % (n,a,c)
	torres_hanoi(n-1,b,a,c)

print torres_hanoi(3,a='Início',b='Auxiliar',c='Fim')

Output:

move disco 1 de Início para Fim

Move disco 2 de Início para Auxiliar

move disco 1 de Fim para Auxiliar

Move disco 3 de Início para Fim

move disco 1 de Auxiliar para Início

Move disco 2 de Auxiliar para Fim

move disco 1 de Início para Fim

[Tharis]

Mas o que é que queres que te expliquem?

[ZNez]

Nao estou a perceber o funcionamento do codigo...

Se apenas quando n=1 é que realiza a opcao 1 porque e q a primeira opcao q ele devolve e essa (se e inicialmente e 3)?

Tambem nao estou a perceber a passagem d poste em poste...

[Betovsky]

#-*-coding:cp1252-*-

def torres_hanoi(n,a,b,c):
   "Implementação das torres de Hanói"
   if n==1:
       print "move disco %d de %s para %s" % (n,a,c)
   else:
       torres_hanoi(n-1,a,c,b)
       print "Move disco %d de %s para %s" % (n,a,c)
       torres_hanoi(n-1,b,a,c)

print torres_hanoi(3,a='Início',b='Auxiliar',c='Fim')

Execução:

print (torres_hanoi(3, inicio, auxiliar, fim))

        - if 3 == 1 (FALSE)

        - torres_hanoi(2, inicio, fim, auxiliar)

                - if 2 == 1 (FALSE)

                - torres_hanoi(1, inicio, auxiliar, fim)

                        - if 1 == 1 (TRUE)

                        - print "move disco 1 de inicio para fim"

                - print "Move disco 2 de inicio para auxiliar"

                - torres_hanoi(1, fim, inicio, auxiliar)

                        - if 1 == 1 (TRUE)

                        - print "move disco 1 de fim para auxiliar"

ETC

Espero que de para veres como funciona a recursividade...

[ZNez]

Não estou a perceber e o segundo passo...

Tipo... o programa esta sempre a chamar-se ate n=1, onde corre a clasula de 'if n=!' e passa o disco de inicio para auxiliar... agora a segunda parte e q n estou a perceber... eu no print nao tenho o b, mas ele aparece no meu output.

[Betovsky]

Não percebi a tua dúvida. O que queres dizer com "eu no print nao tenho o b" ?

[ZNez]

eu dei o valor de 3 a n... ou seja a condicao if n==1 é falsa, passando para a else que volta a chamar a funcao torres_hanoi, mas desta vez com n=2 e como segundo argumento temos c (='fim') e nao b (='auxiliar'), volta a nao ser igual a um, voltando a ir a else, voltando a chamar a funcao.

agora ja temos n==1, entao move o disco de a (='inicio') para c.

ja tendo feito este print porque e q volta a funcao 'else'?  Se e valida para uma das condicoes, nao deveria passar a else...

[Betovsky]

hmm, se percebi  a tua dúvida...

Se tivermos o seguinte bloco de código

if n == 1:
   print "welele!!!"
else :
   print "um"
   print "dois"
   print "tres"

Se o n não for 1, então vai para o else, que em si também é um bloco de código. Vai executar a primeira instrução, ou seja, a função print com o argumento "um". Por acaso não temos aqui o código dessa função, mas imaginemos que ela percorre a string num ciclo e manda para o ecrã letra a letra. Vai chegar a uma altura que mandou as letras todas para o ecrã, e então dá a função por terminada. Nesse instante o programa volta para trás, ou seja, para o ponto onde a função foi chamada (o bloco do else) e executa a instrução seguinte, o print "dois". O mesmo acontece, no fim volta para o else e executa o print "tres".

Imaginemos, que em vez de ter aquele código temos algo deste género:

if n == 1:
   print "welele!!!"
else :
   torres_hanoy(n-1)
   print "dois"
   torres_hanoy(n-1)

Se o n for novamente diferente de 1, a situação é a mesma. Só que no bloco do else em vez da primeira instrução ser a função print, vai ser antes a função torres_hanoy. Mas o mesmo se aplica, no fim de executar a função torres_hanoy, volta para onde estava, ou seja, no else e executa a instrução seguinte, o print e por aí adiante.

No caso específico da tua função torres_hanoy, apesar de ela estar a se chamar a si própria, com o (n-1), no ponto de vista do computador são funções diferentes. Portanto quando o n for 1 e executar o bloco do if e a função terminar e voltar ao ponto atrás onde estava, o n irá estar com o valor de 2.

Deu para perceber?

[ZNez]

Hmm... acho que já estou a perceber. Imaginando que atribuo um valor diferente de 1 (ex.3), a parte do código a ser executada é a do 'else', mas como a primeira linha é a de chamar a própria função com o argumento (n-1), ele chama-a mas admitindo que o valor de n é 1 (caso contrário ficava num ciclo infinito). E isto é válido ate realmente n ser 1 (correndo o print 'dois' tres vezes, para o exemplo dado). Mas nesse caso porque e q s volta a chamar a funcao uma segunda vez?

else :

  torres_hanoy(n-1)                        #devolve 'welele!!!'

  print  "dois"                                  #devolve 'dois'

  torres_hanoy(n-1)                        #devolve 'welele!!!'

ou seja o output devia aparecer:

welele!!!

dois

welele!!!

welele!!!

dois

welele!!!

(...)

e nao...:

welele!!!

dois

welele!!!

dois

welele!!!

dois

welele!!!

[djthyrax]

Vê este exemplo simples de recursividade:

def recursividade(n):
if n == 0:
	print "Acabou!"
else:
	print "n = %i" % n
	recursividade(n-1)

recursividade(5)

Output:

n = 5

n = 4

n = 3

n = 2

n = 1

Acabou!

Isto equivale a fazeres:

n = 5
while n > 0:
print "n = %i" % n
n -= 1

print "Acabou!"

Output:

n = 5

n = 4

n = 3

n = 2

n = 1

Acabou!

Se souberes como funciona aquele loop ou o for(;;[tt][/tt]) em C(++)/PHP, percebes a lógica da recursividade na função de que falas.

Tu chamas a função x() com n = 5, e ela vai chamar-se a si própria com o argumento n-1 enquanto n não for 0.

[ZNez]

ja percebi, obrigado aos dois. tive a fazer o codigo em papel resolvendo todos os passos e descobri o q estava a fazer mal.

🙂