Platzi Promo

Compra Platzi Expert a un precio especial

Aprovecha Platzi Expert a un precio especial

Acelera tu carrera profesional
Compra Platzi Expert a un precio especial

Currency
$269
Termina en:

21H

47M

34S

24

Recursividad con el ejemplo de las Torres de Hanói

704Puntos

hace un año

Curso Gratis de Programación Básica
Curso Gratis de Programación Básica

Curso Gratis de Programación Básica

Programa desde cero, domina Javascript, entiende HTML y aprende de algoritmos. Sí, desde cero. Entenderás la lógica del código, cómo piensan los programadores y cómo programar juegos, proyectos y hasta robots y electrónica. Aprender a programar no es fácil, pero Platzi lo hace efectivo.

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:

  • Se puede mover un solo disco a la vez.
  • Un disco de mayor tamaño no puede estar sobre un disco más pequeño.
  • 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 mínimo 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 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.

Curso Gratis de Programación Básica
Curso Gratis de Programación Básica

Curso Gratis de Programación Básica

Programa desde cero, domina Javascript, entiende HTML y aprende de algoritmos. Sí, desde cero. Entenderás la lógica del código, cómo piensan los programadores y cómo programar juegos, proyectos y hasta robots y electrónica. Aprender a programar no es fácil, pero Platzi lo hace efectivo.
José Luis
José Luis
@j0semart1n

704Puntos

hace un año

Todas sus entradas
Escribe tu comentario
+ 2
Ordenar por:
1
16Puntos

Muy buena aportacion!! Ademas se me hizo muy interesante ya que como se mencionaba que para las torres de hanoi se aplica la recursidad un tema muy genial para aplicarlo en html y javascript

1
3289Puntos

Me toco sacar lapiz y papel para entenderlo perfectamente jajaja. Buen aporte!

0
2788Puntos

Me gusto el post, pero sigo preguntandome, ¿ en que casos es mejor usar un algoritmo recursivo?
Lo pregunto porque entendiendo el concepto de funciones recursivas, pero a la hora de aplicarlo no encuentro el caso concreto , o al menos "el mejor " para que un tipo de algoritmo así sea implementado.

0
9193Puntos
un año

Los algoritmos recursivos son comúnmente usados para el procesamiento con estructuras basadas en arboles ( https://es.wikipedia.org/wiki/Árbol_(informática) ). Por ejemplo, yo desarrolle un algoritmo para realizar el cálculo de cargas de trabajo y tiempo de servicio sobre diagramas de modelado Archimate ( https://en.wikipedia.org/wiki/ArchiMate ), un lenguaje de modelado de arquitecturas empresariales. La aplicación se llama Archi ( https://www.archimatetool.com/ ) y está desarrollada en Java.

0
un año

En los 5 anios que llevo programando solo he usado recursividad en mi trabajo para trabajar con arboles fuera de eso solo ha sido vanidad

0
1109Puntos
un año

Un ejemplo de la vida real con el que me topé en una base de dato. Había una lógica de guardar un elemento llamado dispositivo, dentro de un folder dispositivo, y a su vez este se guardaba en un folder o carpeta, la estructura era de tipo árbol como las carpetas de Windows u otro OS en fin.

Tabla 1
id_folder (PK), id_folder_padre (FK a id_folder), estado

Tabla 2
id_dispositivo (PK), id_folder (FK a Tabla 1:id_folder), estado

Problematica: Se debe mostrar aquellos dispositivos que su estado sea activo y sus folder contenedores activo.

Análisis: Los dispositivos pertenecen a un folder y este folder a su vez dentro de otro folder (sea el mismo u otro folder) y cada dispositivo y/o folder tiene un estado.

Solución: Hacer una función recursiva que reciba el id_folder y verifique el estado del folde actual, si es activo vuelve y llama la función dentro de ella misma con el nuevo id folder padre como parámetro de la función hasta llegar a la raíz o encontrar el estado inactivo para no mostrar el registro; de lo contrario se muestra el dispositivo.

0
15240Puntos
un año

Cuando estas trabajando con grafos es muy util, cabe aclarar que puedes expresar cualquier algoritmo recursivo como uno iterativo, usando una pila para emular la pila del sistema, usualmente eso lo hace mas eficiente porque cada vez que se hace un llamado recursivo, debe guardar todo el estado actual del programa en memoria (incluso las cosas que no son utiles para dicho programa) eso hace que se consuma más memoria.

Ver todas las respuestas

0
506Puntos

Excelente ejemplo de recursividad.
Gracias José Luis.

0
21821Puntos

Recuerdo que aprendí esto en el curso de python