La Torre de Hanói aparece casi siempre cuando se aprende «recursión» en programación. Resolverla a mano lleva cientos de movimientos, pero en un programa se escribe en unas pocas líneas. Veamos cómo funciona, paso a paso. Los postes son izquierda, centro y derecha, y los discos van numerados 1, 2, 3… de menor a mayor.
Qué es la recursión
La recursión consiste en que, dentro del procedimiento que resuelve un problema, se usa el mismo procedimiento con un problema más pequeño. Si sigues reduciendo, llegas a un problema cuya respuesta es inmediata (por ejemplo, con 0 discos no se hace nada), y ahí se detiene.
Pensar la Torre de Hanói con recursión
Piensa en llevar una torre de n discos de la izquierda a la derecha.
- Llevar los n−1 discos de arriba de la izquierda al centro.
- Mover el disco más grande, el n, de la izquierda a la derecha.
- Llevar los n−1 discos del centro a la derecha.
Los pasos 1 y 3 son el problema de «mover una torre de n−1 discos», con la misma forma que el problema original. Solo cambia de qué poste a qué poste se mueve. Por eso, si creas un único procedimiento «mover n discos de un poste a otro usando el tercero», puede llamarse a sí mismo por dentro.
Pseudocódigo
procedimiento hanoi(n, origen, destino, auxiliar):
si n es 0, termina sin hacer nada
hanoi(n − 1, origen, auxiliar, destino) … aparta los n−1 discos de arriba
mueve el disco n de origen a destino
hanoi(n − 1, auxiliar, destino, origen) … devuelve los n−1 discos
hanoi(3, izquierda, derecha, centro) da la secuencia para llevar 3 discos de la izquierda a la derecha Solo con esto se obtiene la secuencia mínima para cualquier número de discos. El código que funciona de verdad en Python y en C está en Resolver la Torre de Hanói en Python y C.
Cómo se ramifican las llamadas
Si escribes cómo se llama a hanoi con 3 discos, sale un árbol como este. Cuanto más sangrada está una línea, más interna es la llamada.
hanoi(3, izquierda→derecha)
├─ hanoi(2, izquierda→centro)
│ ├─ hanoi(1, izquierda→derecha) … 1 a la derecha
│ ├─ 2 al centro
│ └─ hanoi(1, derecha→centro) … 1 al centro
├─ 3 a la derecha
└─ hanoi(2, centro→derecha)
├─ hanoi(1, centro→izquierda) … 1 a la izquierda
├─ 2 a la derecha
└─ hanoi(1, izquierda→derecha) … 1 a la derecha Los «mover» leídos de arriba abajo son, tal cual, la respuesta de 7 movimientos. Cada llamada genera dos llamadas internas, así que cada disco que añades casi duplica el trabajo.
Coste
| Qué se mide | Con n discos |
|---|---|
| Veces que se mueve un disco (movimientos) | 2ⁿ−1 |
| Veces que se llama a hanoi (contando también las llamadas con 0 discos) | 2ⁿ⁺¹−1 |
| Profundidad de las llamadas (lo que hay que recordar a la vez) | n+1 niveles |
Por qué los movimientos son 2ⁿ−1 se demuestra en la fórmula del mínimo de movimientos. El tiempo crece de forma exponencial con el número de discos (O(2ⁿ)), y lo que hay que recordar solo crece de forma proporcional al número de discos (O(n)). Como los movimientos ya son 2ⁿ−1, por mucho ingenio que se use, escribir toda la secuencia lleva al menos ese tiempo.
Una solución sin recursión
También se puede resolver usando solo repeticiones, sin recursión. Es exactamente el procedimiento para resolverlo a mano del artículo sobre cómo resolverlo.
procedimiento hanoi_bucle(n):
decide el sentido del 1 (si n es impar, izquierda→derecha→centro; si es par, izquierda→centro→derecha)
repite para el movimiento m = 1, 2, 3, … , 2ⁿ − 1:
si m es impar, mueve el disco 1 al poste siguiente en el sentido decidido
si m es par, compara los discos de arriba de los dos postes donde no está el 1
y mueve el más pequeño sobre el más grande (o a un poste vacío) No hace falta recordar las llamadas como en la recursión, así que se usa muy poca memoria.
Hallar cualquier movimiento con binario
Hay otro método para hallar directamente qué se hace en el movimiento m sin recorrer los anteriores. Llama a los postes 0, 1 y 2. Para el movimiento m (contando desde 1):
- El disco que se mueve es el número (cantidad de ceros al final de m en binario) + 1.
- El poste de origen es el resto de dividir (m AND (m − 1)) entre 3.
- El poste de destino es el resto de dividir ((m OR (m − 1)) + 1) entre 3.
AND y OR son las operaciones «y» y «o» aplicadas bit a bit en binario. Por ejemplo, con m = 4 (100 en binario) hay 2 ceros al final, así que el disco es el 3. El origen es (4 AND 3) = 0, o sea el poste 0, y el destino es ((4 OR 3) + 1) = 8, cuyo resto al dividir entre 3 es 2, o sea el poste 2.
La secuencia que sale de estas fórmulas lleva la torre del poste 0 al poste 2 si el número de discos es impar, y del poste 0 al poste 1 si es par. Si con un número par de discos quieres llevarla al poste 2, lee la secuencia intercambiando los postes 1 y 2. Esta relación entre el número de movimientos y el binario se explica con detalle en el artículo sobre regularidades.
