CÓMO RESOLVER LA TORRE DE HANOI CON RECURSIÓN

November 13, 2025

Introducción a la Torre de Hanoi

La Torre de Hanoi es un puzzle matemático clásico que ha fascinado a programadores y matemáticos por su simplicidad y profundidad. Este problema, inventado por el matemático francés Édouard Lucas en 1883, consiste en mover una pila de discos de diferentes tamaños desde un poste inicial (fuente) a un poste final (destino), utilizando un poste intermedio como auxiliar. Las reglas son claras y estrictas: solo se puede mover un disco a la vez, cada movimiento implica tomar el disco superior de una pila y colocarlo en otra, y nunca se puede colocar un disco grande sobre uno más pequeño. Este artículo explora cómo resolver este problema utilizando un enfoque recursivo, proporcionando una explicación paso a paso, pseudocódigo, un ejemplo en Ruby y un análisis detallado de la complejidad temporal y espacial.

El objetivo es mover todos los discos desde el poste fuente (A) hacia el poste destino (C), utilizando un poste intermedio (B) como apoyo. Para ilustrar, imaginemos una pila con tres discos. La solución requiere una secuencia precisa de movimientos que respete las reglas mencionadas. A continuación, desglosaremos el problema, construiremos un algoritmo recursivo y analizaremos su eficiencia.

Reglas y concepto básico

El problema de la Torre de Hanoi se basa en tres reglas fundamentales:

Solo se puede mover un disco a la vez.
Cada movimiento consiste en tomar el disco superior de una pila y colocarlo en la parte superior de otra pila.
Un disco más grande no puede colocarse encima de uno más pequeño.

Estas reglas aseguran que el problema tenga una solución única para cualquier número de discos. Para un caso con tres discos, podemos visualizar el proceso como una serie de movimientos entre los postes A (fuente), B (intermedio) y C (destino). Por ejemplo, para mover tres discos de A a C, los pasos serían:

A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C

Estos siete movimientos resuelven el puzzle para tres discos, asegurando que la pila completa se traslade de A a C respetando las reglas. Este proceso puede parecer manual y tedioso, pero su verdadera potencia se revela al generalizarlo mediante un algoritmo recursivo.

¿Qué es un algoritmo?

Un algoritmo es una secuencia de pasos bien definidos que resuelve un problema específico. En el contexto de la programación, un algoritmo es como una receta: una serie de instrucciones que, al seguirse, produce un resultado deseado. Por ejemplo, consideremos una rutina matutina: despertarse, lavarse los dientes, desayunar, vestirse y salir al trabajo. Esta secuencia de tareas puede considerarse un algoritmo cotidiano. En la Torre de Hanoi, el algoritmo define cómo mover los discos de un poste a otro siguiendo las reglas del puzzle.

En términos formales, un algoritmo es una especificación clara y sin ambigüedades para resolver una clase de problemas, que puede involucrar cálculos, procesamiento de datos o razonamiento automatizado. La solución de la Torre de Hanoi es un excelente ejemplo de un algoritmo que utiliza recursión para dividir el problema en subproblemas más pequeños.

Entendiendo la recursión

La recursión es una técnica donde una función se llama a sí misma para resolver una versión más pequeña del mismo problema. En la Torre de Hanoi, la recursión es clave porque el proceso de mover n discos puede descomponerse en mover n-1 discos dos veces, más un movimiento adicional del disco más grande. Para que la recursión funcione, debe haber una condición de terminación que detenga las llamadas recursivas. En este caso, la condición de terminación ocurre cuando solo queda un disco, ya que mover un solo disco es trivial: simplemente se traslada del poste fuente al destino.

Por ejemplo, para un solo disco, el movimiento es directo:

A -> C

Para más discos, el problema se divide en tres pasos recursivos:

Mover n-1 discos desde el poste fuente al poste intermedio, usando el destino como auxiliar.
Mover el disco más grande (el n-ésimo disco) desde el poste fuente al destino.
Mover los n-1 discos desde el poste intermedio al destino, usando el fuente como auxiliar.

Esta descomposición es la base del algoritmo recursivo que resolverá el problema para cualquier número de discos.

Construyendo el algoritmo en pseudocódigo

Para formalizar la solución, escribiremos un algoritmo en pseudocódigo, que es una forma de expresar la lógica de un programa en lenguaje natural antes de implementarlo en un lenguaje de programación. El pseudocódigo para la Torre de Hanoi se puede estructurar así:

Procedimiento torre(numero_discos, fuente, intermedio, destino)
   Si numero_discos es igual a 1 Entonces
      Mover disco de fuente a destino
   Sino
      torre(numero_discos - 1, fuente, destino, intermedio)
      Mover disco de fuente a destino
      torre(numero_discos - 1, intermedio, fuente, destino)
   Fin Si
Fin Procedimiento

Este pseudocódigo define una función torre que toma cuatro parámetros: el número de discos y los nombres de los postes fuente, intermedio y destino. La condición de terminación es cuando numero_discos es 1, en cuyo caso se mueve el disco directamente. Para casos con más discos, la función se llama recursivamente dos veces, con un movimiento intermedio del disco más grande.

Implementación en Ruby

Ahora que entendemos la lógica, implementemos el algoritmo en Ruby. El siguiente código muestra cómo resolver la Torre de Hanoi para un número arbitrario de discos:

def torre(numero_discos, fuente, intermedio, destino)
  if numero_discos == 1
    puts "#{fuente} -> #{destino}"
    return
  end
  torre(numero_discos - 1, fuente, destino, intermedio)
  puts "#{fuente} -> #{destino}"
  torre(numero_discos - 1, intermedio, fuente, destino)
  nil
end

# Ejemplo de uso
torre(3, 'A', 'B', 'C')

Al ejecutar este código con tres discos, la salida será:

A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C

Este código imprime los movimientos necesarios para resolver el puzzle. Cada línea representa un movimiento de un disco desde un poste fuente a un poste destino. La recursión maneja automáticamente la secuencia correcta, asegurando que las reglas se respeten.

Visualizando el proceso recursivo

Para comprender mejor cómo funciona la recursión, imaginemos el árbol de llamadas para tres discos. El proceso puede representarse como una estructura jerárquica donde cada llamada a la función torre genera dos nuevas llamadas recursivas, excepto en el caso base (un disco). El árbol de recursión para tres discos tiene la siguiente forma:

Primera llamada: torre(3, A, B, C)
- torre(2, A, C, B)
  - torre(1, A, B, C) → Mueve disco 1 de A a C
  - Mueve disco 2 de A a B
  - torre(1, C, A, B) → Mueve disco 1 de C a B
- Mueve disco 3 de A a C
- torre(2, B, A, C)
  - torre(1, B, C, A) → Mueve disco 1 de B a A
  - Mueve disco 2 de B a C
  - torre(1, A, B, C) → Mueve disco 1 de A a C

Este árbol muestra cómo el problema se descompone en subproblemas más pequeños, resolviendo cada uno recursivamente hasta llegar al caso base.

Análisis de complejidad temporal

La complejidad temporal mide cuánto tiempo tarda un algoritmo en ejecutarse en función del tamaño de la entrada. En la Torre de Hanoi, el tamaño de la entrada es el número de discos (n). Para calcular la complejidad, observemos que cada llamada a la función torre realiza:

Dos llamadas recursivas para n-1 discos.
Una operación constante para mover un disco.

Matemáticamente, el tiempo requerido para mover n discos, denotado como T(n), se expresa como:

T(n) = 2 * T(n-1) + c

Donde c es una constante que representa el tiempo de mover un disco, y T(0) = c' (otra constante para el caso base). Resolviendo esta recurrencia:

Para n = 1: T(1) = 2 * T(0) + c = 2c' + c
Para n = 2: T(2) = 2 * T(1) + c = 2(2c' + c) + c = 4c' + 3c
Para n = 3: T(3) = 2 * T(2) + c = 2(4c' + 3c) + c = 8c' + 7c

Generalizando, el número de movimientos para n discos es 2^n - 1. Por lo tanto, la complejidad temporal es O(2^n), lo que indica que el tiempo crece exponencialmente con el número de discos. Esto hace que el algoritmo sea computacionalmente costoso para grandes valores de n.

Por ejemplo, para 3 discos se requieren 7 movimientos, para 4 discos se requieren 15 movimientos, y para 10 discos se requieren 1023 movimientos. Este crecimiento exponencial es típico en problemas resueltos mediante recursión pura, lo que resalta la importancia de entender las limitaciones del enfoque.

Análisis de complejidad espacial

La complejidad espacial mide la cantidad de memoria que utiliza el algoritmo. En el caso de la Torre de Hanoi, la memoria se consume principalmente en la pila de llamadas recursivas. Cada llamada a la función torre almacena parámetros (número de discos, nombres de los postes) y variables locales, que ocupan una cantidad constante de espacio, digamos k.

Dado que las dos llamadas recursivas no se ejecutan simultáneamente (la segunda comienza después de que termina la primera), la profundidad máxima de la pila de recursión es n. Por lo tanto, la complejidad espacial se calcula como:

S(n) = S(n-1) + k
S(0) = k

Resolviendo:

Para n = 1: S(1) = S(0) + k = k + k = 2k
Para n = 2: S(2) = S(1) + k = 2k + k = 3k
Para n = 3: S(3) = S(2) + k = 3k + k = 4k

La complejidad espacial es O(n), lo que significa que el uso de memoria crece linealmente con el número de discos. Esto es más eficiente que la complejidad temporal, ya que la memoria adicional requerida es proporcional a n, no exponencial.

Aplicaciones prácticas y limitaciones

Aunque la Torre de Hanoi es un puzzle académico, su solución recursiva tiene aplicaciones en la enseñanza de conceptos fundamentales de programación, como la recursión, la división de problemas y el análisis de complejidad. Además, el problema ilustra cómo los algoritmos recursivos pueden ser elegantes pero ineficientes para grandes entradas debido a su complejidad exponencial.

En la práctica, los algoritmos con complejidad O(2^n) son inviables para grandes valores de n. Por ejemplo, mover 64 discos (como en la leyenda original de la Torre de Hanoi) requeriría 2^64 - 1 movimientos, un número astronómico que tomaría miles de millones de años en completarse incluso en una computadora moderna. Esto resalta la importancia de buscar soluciones iterativas o algoritmos más eficientes para problemas similares en aplicaciones reales.

Sin embargo, la recursión sigue siendo una herramienta poderosa para problemas que se descomponen naturalmente en subproblemas, como el ordenamiento por mezcla (merge sort) o el recorrido de árboles. La Torre de Hanoi es un excelente punto de partida para aprender a diseñar y analizar algoritmos recursivos.

Ejemplo extendido en Python

Para complementar la implementación en Ruby, veamos cómo resolver la Torre de Hanoi en Python. Este ejemplo incluye un contador para mostrar el número total de movimientos:

def torre_hanoi(n, fuente, intermedio, destino, contador):
    if n == 1:
        print(f"Mover disco 1 de {fuente} a {destino}")
        contador[0] += 1
        return
    torre_hanoi(n-1, fuente, destino, intermedio, contador)
    print(f"Mover disco {n} de {fuente} a {destino}")
    contador[0] += 1
    torre_hanoi(n-1, intermedio, fuente, destino, contador)

# Ejemplo de uso
contador = [0]  # Usamos una lista para modificar el contador en la recursión
torre_hanoi(3, 'A', 'B', 'C', contador)
print(f"Total de movimientos: {contador[0]}")

Salida:

Mover disco 1 de A a C
Mover disco 2 de A a B
Mover disco 1 de C a B
Mover disco 3 de A a C
Mover disco 1 de B a A
Mover disco 2 de B a C
Mover disco 1 de A a C
Total de movimientos: 7

Este código en Python es similar al de Ruby, pero incluye un contador para ilustrar cómo rastrear el número de movimientos. La salida muestra cada movimiento y confirma que se requieren 7 movimientos para 3 discos, coincidiendo con la fórmula 2^n - 1.

Optimizaciones y enfoques alternativos

Aunque la solución recursiva es la más intuitiva para la Torre de Hanoi, existen enfoques iterativos que pueden ser más eficientes en términos de tiempo de ejecución para ciertos casos. Por ejemplo, un algoritmo iterativo basado en un patrón binario puede generar los movimientos sin usar la pila de recursión. Sin embargo, estos enfoques suelen ser más complejos de entender y no ofrecen una mejora significativa en la complejidad temporal, que sigue siendo O(2^n).

Otra optimización podría involucrar la memorización de movimientos para casos específicos, pero dado que la Torre de Hanoi tiene una solución determinista, esta técnica no aporta beneficios significativos. En general, el enfoque recursivo sigue siendo el estándar debido a su claridad y simplicidad.

Conclusiones

La Torre de Hanoi es un problema fascinante que combina matemáticas, lógica y programación. Su solución recursiva ilustra cómo un problema complejo puede descomponerse en subproblemas más pequeños, utilizando la recursión como una herramienta poderosa. A través de este artículo, hemos explorado las reglas del puzzle, desarrollado un algoritmo en pseudocódigo, implementado una solución en Ruby y Python, y analizado la complejidad temporal (O(2^n)) y la complejidad espacial (O(n)). Aunque el algoritmo recursivo es elegante, su crecimiento exponencial lo hace impractical para grandes entradas, lo que resalta la importancia de evaluar la eficiencia al diseñar soluciones. Este problema sigue siendo un pilar en la enseñanza de algoritmos y un recordatorio de cómo la simplicidad puede esconder una profunda complejidad computacional.