libro de economia

Notación
Los discos se numerarán de 1 a 8 (o a n, en general), empezando por el más pequeño. Los postes (que se supondrán alineados de izquierda a derecha) serán marcados con letras mayúsculas (A, B y C). El inicial será A y el objetivo C.
 
fig. 1
Un algoritmo recursivo
La Torre de Hanoi suele aparecer como ejemplo para ilustrar el concepto de recursión en los cursos de programación decomputadoras, 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.
 
fig. 2
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.
 
fig. 3
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 trasladar una torre equivale a trasladar un solo disco (esto ocurre cuando la torre es de un solo disco, claro). En resumen, elalgoritmo 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 auxiliarX.
Este algoritmo siempre me ha parecido sorprendente, parece más la definición de un problema que su resolución. Si eres como yo tendrás que implementarlo en un lenguaje de programación concreto para convencerte de que funciona. 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 ejecutarseel algoritmo para n+1 se llama a sí mismo dos veces para n, más un movimiento del disco n+1. Así que
M3(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ñospara 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 «pocoeconómicos», en el sentido de que consumen bastante memoria (y es que ellos también necesitan «tomar notas»). 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...