13

TUTORIAL AVANZADO: Recursividad y Torres de Hanói

Después de terminar el “Curso de Programación Básica” eché en falta alguna explicación al concepto de recursividad (que aunque de forma indirecta se ha explicado) se trata de una noción fundamental para todos aquellos que quieran ser programadores y profesionales en el mundo de la tecnología.

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 ilustratorio de como 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 y 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:

  1. Se puede mover un solo disco a la vez.
  2. Un disco de mayor tamaño no puede estar sobre un disco más pequeño.
  3. Solo se puede desplazar el disco que esté más arriba en cada varilla.

De esto se puede deducir que según el número de discos que haya en la torre, se podrá resolver el problema con un número de pasos minimo que corresponde con la siguiente relación

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).

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 Javascript, 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): goo.gl/Ur53Y3

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 mando 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 y 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.

Escribe tu comentario
+ 2
0
231Puntos

Gracias, me ayudó bastante