La recursividad es una herramienta fundamental en matemáticas y programación que nos permite definir funciones o procesos en términos de sí mismos. Un ejemplo clásico para entender este concepto es el cálculo del factorial de un número. En lugar de multiplicar todos los números desde 1 hasta n de forma explícita, podemos definir el factorial de n como n multiplicado por el factorial de n-1. Esto nos lleva a una definición sencilla y elegante, siempre que establezcamos un caso base para evitar una recursión infinita. Por ejemplo, el factorial de 0 es 1, y este es el punto donde la función deja de llamarse a sí misma.
Pero la recursividad no se limita a cálculos matemáticos simples. Un problema lógico que se beneficia enormemente de este enfoque es el de las Torres de Hanoi. En este desafío, tenemos tres torres y una serie de discos apilados en forma de pirámide en la primera torre, con discos de tamaños decrecientes de abajo hacia arriba. El objetivo es trasladar toda la pirámide a la tercera torre, respetando dos reglas: primero, la torre destino debe mantener la misma estructura piramidal, es decir, los discos deben estar ordenados de menor a mayor de arriba hacia abajo; segundo, solo podemos mover un disco a la vez y nunca colocar un disco más grande sobre uno más pequeño.
Para quienes no hayan experimentado este problema, puede resultar complicado avanzar sin atascarse. Sin embargo, la recursividad nos ofrece una solución clara y eficiente. La clave está en dividir el problema grande en subproblemas más pequeños. Si queremos mover una pirámide de n discos de una torre origen a una torre destino, podemos hacerlo en tres pasos: primero, mover los primeros n-1 discos a la torre auxiliar; segundo, mover el disco más grande que queda en la torre origen a la torre destino; y tercero, mover los n-1 discos desde la torre auxiliar a la torre destino. Este enfoque es recursivo porque para mover los n-1 discos también aplicamos la misma estrategia.
Es importante definir un caso base para esta recursión: cuando solo hay un disco en la torre origen, simplemente lo movemos a la torre destino sin pasos intermedios. Esto evita que la función se llame a sí misma indefinidamente.
Para implementar esta solución en código, podemos representar cada disco con un número entero, donde los números más grandes corresponden a discos más grandes. Las torres se pueden modelar como pilas, ya que solo podemos acceder al disco en la cima, lo que refleja la restricción física del problema.
El pseudocódigo para la función recursiva Hanoi sería algo así:
void Hanoi(int n, Stack origen, Stack destino, Stack auxiliar) {
if (n == 1) {
// Mover disco de origen a destino
destino.push(origen.pop());
} else {
// Mover n-1 discos de origen a auxiliar
Hanoi(n - 1, origen, auxiliar, destino);
// Mover disco restante de origen a destino
destino.push(origen.pop());
// Mover n-1 discos de auxiliar a destino
Hanoi(n - 1, auxiliar, destino, origen);
}
}
Este algoritmo nos permite resolver el problema para cualquier número de discos.
Además, podemos calcular el número mínimo de movimientos necesarios para trasladar n discos. Para un disco, solo se necesita un movimiento. Para dos discos, tres movimientos. Para tres discos, siete movimientos. Para cuatro, quince. Observando esta progresión, notamos que el número de movimientos mínimos es siempre 2^n - 1. Por ejemplo, para siete discos, se requieren 127 movimientos.
Existe una leyenda que añade un toque histórico y místico a este problema. Se dice que en un templo indio, un rey ordenó a los monjes mover 64 discos de oro siguiendo las reglas de las Torres de Hanoi. Según la historia, cuando los monjes terminen de mover todos los discos, el mundo llegará a su fin. Sin embargo, según la fórmula, para mover 64 discos se necesitan 2^64 - 1 movimientos, un número tan enorme que incluso si los monjes hicieran un movimiento por segundo, tardarían casi 585.000 millones de años en completar la tarea.
Curiosamente, aunque la leyenda tiene raíces en la India, el nombre Torres de Hanoi proviene de una versión que sitúa el templo en Hanoi, la capital de Vietnam. Así, el problema ha adoptado este nombre en honor a esa versión de la historia.
Con este entendimiento, podemos apreciar cómo la recursividad no solo simplifica problemas matemáticos, sino que también nos ayuda a resolver desafíos lógicos complejos como las Torres de Hanoi, dividiendo el problema en partes manejables y aplicando soluciones repetitivas hasta alcanzar el objetivo final.