Torres de Hanoi en Lisp

Hola,

La ventaja de que nadie siga tu blog es que puedes cambiar de tema sin que nadie se flipe.

Por eso vuelvo al tema del Lisp. Que yo recuerde la última vez lo deje en la función fibonacci recursiva.

Hoy vamos a resolver el primer problema puramente recursivo. Y ¿eso que significa? Que no se si está matematicamente demostrado o no (creo que SI, pero tampoco importa), pero cualquier problema que se puede resolver de forma recursiva puede resolverse también de forma no recursiva.

Ahora bien, en un problema puramente recursivo lo que ocurre es que la solución revursiva es sencilla de entender y en cambio la no recursiva se vuelve enormemente complicada.

Pensemos en el problema tal y como lo planteé en su día: http://aitoreus.blogspot.com/2006/02/torres-de-hanoi.html

O sea, tenemos 3 torres. Las llamaremos A, B y C.
Hay 64 discos montados en la torre A que hay que llevar a la torre C.
Las reglas son 2:

1. No se puede mover más de un disco cada vez.
2. No se puede colocar un disco mayor sobre otro menor.

No lo he dicho, pero los 64 discos que inicialmente están en la torre A se encuentran cumpliendo la regla 2.

Tenemos una pista buenísima y es que el problema es RECURSIVO.

O sea, podemos encontrar la solución pensando en verde.

Ummm,

Como empezaríamos a hacerlo manualmente...

Espera tengo una idea, en temas de recursividad muchas veces hay que simplificar el problema.

Si sólo hubiera un disco en la torre A... Movemos el disco a la torre C y problema terminado.

Si hay 2 discos. Movemos el primero (el más pequeño) a la torre B. Luego el segundo (el más grande que estaba debajo) a la torre C. Por último el pequeño a la torre C y problema terminado.

Si hay 3 discos. ¿Movemos el primero a la torre B?. Bueno, entonces el siguiente disco (el mediano de los 3) va a la torre C. Luego estamos obligados a colocar el pequeño de la torre B en la torre C. Una vez hecho esto podemos sacar el grande y ponerlo en B. Ahora bien, hay que librar la torre C de los 2 discos y eso nos lleva a un montón de movimientos. Era mejor hacer exactamente lo mismo pero empezando a mover a la torre C. Así los 2 discos pequeños se quedan colocaditos en B y la C está libre para el grande.

Bueno, ya sólo queda mover el grande al C, el pequeño al A, el mediano al C y el pequeño al C.

¿Que ocurre en el caso de 4 discos? Ahora si que toca pensar, ya que el número de movimientos puede ser brutal.