Ejemplo 10 - Utilización de recursividad para resolución de problemas - Análisis

La mejor manera de iniciar el análisis del problema es haciendo casos sencillos. Sabemos que la solución más efectiva se realiza con 2n - 1 movidas. Entonces en el caso n=2, se debería llegar a la solución con 3 movidas:

  1. Mover disco 1 al intermedio.
  2. Mover disco 2 al final.
  3. Mover disco 1 al final.

De manera similar podemos mover 2 discos de cualquier torre a cualquier otra. Pensemos ahora el caso n=3. Este se resuelve en 7 movidas. La complejidad aumenta... pero si planteamos el problema de manera recursiva, su complejidad se reduce significativamente:

  1. Mover discos 1 y 2 al intermedio.
  2. Mover disco 3 al final.
  3. Mover discos 1 y 2 al final.

¿Pero cómo se mueven los discos 1 y 2? Con los movimientos que usamos en el caso n=2. En general, el problema se puede plantear así:

Para mover los discos 1,2,3,...,n de la torre A a la torre B, hacer lo siguiente:

  1. Mover los discos 1,2,3,...,n-1 de la torre A a la torre C.
  2. Mover el disco n de la torre A a la torre B.
  3. Mover los discos 1,2,3,...,n-1 de la torre C a la torre B.

La condición de parada se puede definir como el movimiento de un disco: el disco 1.