Algoritmo recursivo

La Torre de Hanoi suele aparecer como ejemplo para ilustrar el concepto de recursión en los cursos de programación de computadoras, ya que existe un algoritmo recursivo sorprendentemente simple que lo resuelve (por si alguien no lo sabe, un algoritmo es recursivo si se llama a sí mismo en alguno de sus pasos). Supongamos que queremos trasladar los ocho discos del poste A al poste C. Como el disco 8 siempre está abajo del todo, la única forma de hacerlo es trasladar primero la torre de siete discos 1...7 al poste B. Entonces podremos llevar el disco 8 de A a C, y para terminar tendremos que trasladar de nuevo la torre 1...7, ahora de B a C.

Pero los discos 1...7 forman una torre totalmente similar a la inicial, así que en dos de los tres pasos anteriores nos enfrentamos con un problema análogo al original. De hecho, puede resolverse de la misma forma, trasladando ahora la torre 1...6. Por ejemplo, el primer paso (trasladar la torre 1...7 de A a B) se puede descomponer en estos tres pasos.

Por supuesto, en dos de estos tres pasos nos volvemos a encontrar con el problema original, ahora con n = 6. El proceso no es infinito, ya que llega el momento en que una torre equivale a trasladar un solo disco (esto ocurre cuando la torre es de un solo disco, claro). En resumen, el algoritmo recursivo es el siguiente.

Algoritmo para trasladar la torre 1...n del poste X al poste Z, usando como auxiliar el poste Y.

1.-Si n = 1, lleva el disco 1 de X a Z y termina.
2.-Traslada la torre 1...n−1 usando este mismo algoritmo, de X a Y, usando como auxiliar Z.
3.-Lleva el disco n de X a Z.
4.-Traslada la torre 1...n−1 usando este mismo algoritmo, de Y a Z, usando como auxiliar X.

Este algoritmo siempre me ha parecido sorprendente, parece más la definición de un problema que su resolución. En realidad, lo único que hace es especificar unos pasos inevitables. Por ejemplo, como vimos antes, para resolver el puzzle es obligatorio llevar el disco n de A a C, y para ello es obligatorio llevar antes la torre 1...n a B, etc. La secuencia de movimientos que produce este algoritmo es la única solución óptima (o sea, de longitud mínima) posible. El número de movimientos es M3(n) = 2n−1, como se puede demostrar fácilmente por inducción sobre el número de discos.

Se cumple para n = 1
M3(1) = 1 = 21−1.
Si se cumple para n, se cumple para d+1


Al ejecutarse el algoritmo para n+1 se llama a sí mismo dos veces para n, más un movimiento del disco n+1. Así queM3(n+1) = 2 × M3(n) + 1 = 2 × (2n−1) + 1 = 2n+1−2+1 = 2n+1−1

Para n = 8 el número de movimientos es de 28−1 = 255. Para n = 64, de 264−1 = 18.446.744.073.709.551.615. Si los bramanes de Benarés cambiaran un disco de sitio cada segundo necesitarían más de quinientos ochenta mil millones de años para terminar su tarea, unas cuarenta veces la edad del Universo.

Los algoritmos recursivos funcionan bien con ordenadores, pero son difíciles de aplicar para un ser humano. Si intentas resolver la torre de ocho discos aplicando el método descrito es fácil que te pierdas a no ser que vayas tomando notas de por dónde vas. Incluso para los ordenadores los algoritmos recursivos suelen ser poco económicos, en el sentido de que consumen bastante memoria (y es que ellos también necesitan. La alternativa a los algoritmos recursivos son los iterativos, en los que no hay llamadas a sí mismo, sino uno o varios bucles. Muy a menudo no existe o no se conoce una alternativa iterativa para un algoritmo recursivo, y cuando sí se conoce, suele ser mucho más complicada que la versión recursiva. Sin embargo, en el caso de la Torre de Hanoi, existen varios algoritmos iterativos muy simples.