Si estás empezando en el mundo del desarrollo web, probablemente estás tomando el Curso de Programación Básica. Al terminar de tomar un curso es importante repasar algunos conceptos fundamentales de programación, y en este caso veremos la recursividad.
La recursión o recursividad en programación es un concepto matemático que podemos definir como una función que se puede expresar con términos de la propia función. Para explicar mejor el concepto, usaremos la definición de lo que es un factorial:
Un factorial es el productorio de k, siendo k=1 hasta n siendo n números enteros.
Un productorio es una notación matemática (una representación) de la multiplicación de una cantidad arbitraria.
Un ejemplo ilustrativo de cómo funciona es ver ejemplos sobre los factoriales de 1, 2, 3, 4 y 5:
1! = 1
2! = 1 * 2 = 2
3! = 1 * 2 * 3 = 6
4! = 1 * 2 * 3 * 4 = 24
5! = 1 * 2 * 3 * 4 * 5 = 120
La recursividad funciona en el caso de 5! (factorial de 5) se puede definir como:
5! = 4! * 5
4! = 3! * 4
3! = 2! * 3
2! = 1! * 2
1! = 0! * 1
0! = 1
Después de haber explicado este concepto, voy a proponer la realización de un programa que resuelva un problema muy conocido en matemáticas y que es conocido por Las Torres de Hanói.
Se trata de un rompecabezas, propuesto por el matemático Édouard Lucas, un juego que consiste en tres varillas verticales y una de las varillas tiene un indeterminado número de discos apilados de forma decreciente, de abajo hacia arriba. El objetivo es trasladar todos estos discos a una de las varillas verticales que está vacía. La varilla central se usa de apoyo para trasladar los discos y se tiene que hacer conforme a unas reglas:
Con 1 disco, es necesario 1 paso.
Con 2 discos, es necesario 3 pasos.
Con 3 discos, es necesario 7 pasos.
Con 4 discos, es necesario 15 pasos.
Esto se puede hacer con la fórmula P(n) = 2^n - 1. Siendo P(n) la función y n el número de discos (se lee 2 elevado a n, es decir, 2 multiplicado por 2, n veces, menos 1).
Te puede interesar: aprende a armar el cubo de rubik paso a paso
Sabiendo esto, vamos a programar un ejemplo que resuelva el problema de Las Torres de Hanói con 4 discos. Vamos a programar en HTML y JavSscript, el primer archivo en HTML, yo lo he llamado “hanoi.html” y el código sería el siguiente:
Y el archivo JavaScript lo he llamado “torre.js” y el código es el siguiente:
El programa está preparado para 4 discos y este sería el resultado:
El programa muestra el uso de la recursividad. Se ha hecho de la manera más simple ya que, aunque con el curso hemos tenido conocimientos sobre como dibujar usando Canvas, esto se deja como propuesta para miembros de la comunidad que se atrevan a implementar un programa más sofisticado.
Los archivos con el contenido del código podéis descargarlo desde aquí (está comprimido).
Algunos sitúan el origen de la leyenda en la India o en Hanói (Vietnam), pero resulta que esta cuenta que un rey indio mandó instalar en un templo 64 discos de oro y que cuando se instalase el último disco en la torre llegaría el fin del mundo. Si se tardase un segundo en realizar un movimiento, se tardaría de forma aproximada unos 584.942.417.355 años. Para que te hagas una idea, el universo se sabe de forma aproximada que tiene una edad de 15.000 millones de años y nuestro Sol unos 5.000 millones de años. Para mover los discos de la leyenda se tardaría ¡¡584.942 millones de años!!.
Espero que este tutorial haya sido didáctico para los miembros de la Comunidad.
La función recursiva es de gran importancia a la hora no solo de reutilizar código sino también a la hora de manejar sucesiones o reglas de series. En la generación de movimientos con ordenamiento se maneja una ley o regla que permite ordenar los anillos en el menor tiempo posible y con orden de tamaño según cantidad de anillos. Comparto un programa en javascript que permite la generación de movimientos totales de una torre de Hanoi a través de un programa recursivo >> https://tutorias.co/recursividad-javascript-torres-de-hanoi/