Torres de Hanoi Python: comprensión de la recursión

Soy completamente nuevo en Python y actualmente estoy repasando un tutorial sobre Las torres de Hanoi y la recursión. Pensé que entendía la recursión hasta que dieron este ejemplo:

def moveTower(height,fromPole, toPole, withPole): if height >= 1: moveTower(height-1,fromPole,withPole,toPole) moveDisk(fromPole,toPole) moveTower(height-1,withPole,toPole,fromPole) #print(withPole) def moveDisk(fp,tp): print("moving disk from",fp,"to",tp) moveTower(3,"A","B","C") 

que imprime los movimientos correctos para resolver las torres del problema de hanoi con 3 discos: mover el disco de A a B mover el disco de A a C mover el disco de B a C mover el disco de A a B mover el disco de C a A mover el disco de C a B moviendo el disco de A a B

Mi pregunta es, ¿cómo lo hace? ¿Podría alguien repasar las líneas de código para que entienda cómo imprime los movimientos correctos? Estoy confundido principalmente con cómo el valor de fp y tp puede cambiar de A a B a C Lo siento si esto es un poco de una pregunta amplia! Cualquier ayuda sería muy apreciada!

En este caso simple, solo puede visualizar lo que sucede usando las print apropiadas, como esta:

 def moveTower(height,fromPole, toPole, withPole): if height >= 1: print( " "*(3-height), "moveTower:", height, fromPole, toPole ) moveTower(height-1,fromPole,withPole,toPole) moveDisk(fromPole,toPole,height) moveTower(height-1,withPole,toPole,fromPole) #print(withPole) def moveDisk(fp,tp,height): print(" "*(4-height), "moving disk", "~"*(height), "from",fp,"to",tp) moveTower(3,"A","B","C") 

La salida es:

 moveTower: 3 AB moveTower: 2 AC moveTower: 1 AB moving disk ~ from A to B moving disk ~~ from A to C moveTower: 1 BC moving disk ~ from B to C moving disk ~~~ from A to B moveTower: 2 CB moveTower: 1 CA moving disk ~ from C to A moving disk ~~ from C to B moveTower: 1 AB moving disk ~ from A to B 

Esto es lo que hace. La posición inicial es:

 A|321 B| C| 

luego con moveTower(2,fromA,toC, withB) el resultado es:

 A|3 B| C|21 

entonces, moveDisk(fromA, toB) hace

 A| B|3 C|21 

y finalmente moveTower(2,fromC, toB) termina el juego.

 A| B| C|321 

Esa es la solución habitual para Hanoi: mueva la torre de altura h-1 al withPole , mueva el disco más grande al endPole y mueva la torre de altura h-1 al endPole .

Eso funciona porque puede mover cada disco de la torre de altura h-1 en el disco más grande.

Para hacer moveTower(height-1,w,x) se le permite colocar todo el disco restante en las 3 torres.

Así que moverá moveTower(height-2,y,z) luego moverá el segundo disco más grande a su destino y moverá la torre de altura-2 nuevamente.

Edit: El diagtwig en este enlace describe mejor lo que estoy tratando de decir (“Una imagen vale más que mil palabras”).

Si sabe de mover una torre de height-1 , entonces solo haga los 3 pasos descritos en su algoritmo. moveDisc es el “caso base” (subir el primer paso), moveTower es la recursión (cómo pasar del paso n al n+1 ).

El tema se trata aquí , sin embargo, el enfoque recursivo puede ser confuso si uno no está familiarizado con el concepto. El algoritmo funciona primero moviendo recursivamente todo menos el último disco (una instancia de problema más pequeña) a través de la memoria caché, luego “en realidad” moviendo el último disco a la barra de destino y luego moviendo la torre a la barra inicial. En efecto, al confiar en la recursión, el disco en la parte inferior se mueve a la trazabilidad de destino, lo cual es imposible de hacer directamente ya que no es un movimiento válido. En la llamada recursiva, las tres clavijas cambian los roles de tal manera que siempre una clavija vacía se convierte en el caché. Esto se entiende mejor si se imagina que las clavijas no están dispuestas en la línea sino en un círculo. A diferencia de otros problemas, aquí la llamada recursiva viene primero y luego se realiza el movimiento “real”.

La pregunta puede verse como un duplicado de esta pregunta.

Debe imprimir la llamada de cada moveTower para ver los cambios en sus argumentos. La recursión típicamente propaga cambios a través de argumentos. Un número de secuencia es útil para mostrar el orden (por supuesto, la impresión en la consola también está ordenada).

 def seq_nummer(): num = 0 while True: num += 1 yield num seq_num = seq_nummer() def moveTower(height, fromPole, toPole, withPole): print("seq: %d" % seq_num.next()) print("height: %d, fromPole: %s, toPole: %s, withPole: %s" % (height, fromPole, toPole, withPole)) if height >= 1: moveTower(height-1, fromPole, withPole, toPole) moveDisk(fromPole, toPole) moveTower(height-1, withPole, toPole, fromPole) def moveDisk(fp,tp): print("moving disk from",fp,"to",tp) moveTower(3,"A","B","C") 
 moveTower(height-1,fromPole,withPole,toPole) 

Mueva todos los discos excepto uno desde el polo inicial al polo intermedio, utilizando el tercer polo.

 moveDisk(fromPole,toPole) 

Mueve el último disco del polo inicial al polo final. Ahora el último disco está en su posición correcta y no es necesario moverlo.

 moveTower(height-1,withPole,toPole,fromPole) 

Mueva todos los discos del polo intermedio al polo final, utilizando el primer polo si es necesario.