13 jul. 2015

Programación en C – Recursividad – Torres de Hanói

Hola a todos, en esta ocasión les presento las Torres de Hanói con Recursividad en el lenguaje de Programación C estructurado.

Comencemos por explicar que es la Recursividad en un lenguaje de programación.

La Recursividad consiste en una función la cual se llama a sí misma, con una validación para salir del bucle recursivo. Esto suena muy confuso, veamos un ejemplo para verlo más claro.


Esta función resuelve el factorial de un número, recordemos, el factorial es la multiplicación de todos los enteros del 1 al número elegido. Por ejemplo, el factorial de 5 es 1*2*3*4*5 = 120.

Esta función recibe por parámetro un entero y valida, si el numero es 1 o menor que 1 devuelve un 1, ahora, si es mayor a 1 va a devolver el valor pasado por parámetro multiplicando factorial(numero-1). En esta línea de código se encuentra la verdadera magia de la recursividad que pasaremos a explicar.

Supongamos como el ejemplo anterior que le pasamos a la función el valor 5, este valor es mayor que 1, por lo que la función va a devolver 5 * factorial (4), esto realiza una nueva llamada a la función, esta vez con el valor 4, la función factorial (4) va a devolver 4 * factorial (3), nuevamente, otra llamada a la función. Siguiendo con el análisis, la función factorial (3) devolverá 3 * factorial (2), factorial (2) devolverá 2 * factorial (1). Y finalmente, factorial (1) es un valor igual o menor a 1, por eso devolverá 1. Hasta acá explicamos cómo se llama a sí misma la función y los valores que ira devolviendo cada llamada.

Ahora, el programa lo que hará es resolver la última función que fue llamada, esta es factorial (1), como dijimos antes, esta función devuelve el valor 1. Ahora el programa va a resolver la función llamada antes, factorial (2), cuyo resultado es 2 * factorial (1), pero como factorial (1) ya nos devolvió valor, factorial (2) devolverá 2 * 1, nuevamente, la función anterior a estas fue factorial (3), la cual devuelve 3 * factorial (2), es decir, 3 * 2,
Luego factorial (4) devolverá 4 * factorial (3), es decir, 4 * 6. Terminando este proceso llegamos a factorial (5), la primer función llamada, y al ser recursiva, la ultima en resolverse, la cual devolverá 5 * factorial (4), 5 * 24 = 120, siendo 120 el factorial de 5. De esta forma funciona la recursividad.


Ahora que sabemos básicamente que es y cómo funcionan los algoritmos recursivos, pasaremos a un ejemplo más complejo e interesante, las Torres de Hanói.

Las Torres de Hanói son un rompecabezas o juego matemático. Este juego de mesa se trata de N discos de radio creciente que se apilan insertándose en una de las tres estacas de un tablero. El objetivo del juego es crear la pila en otra de las estacas siguiendo ciertas reglas.

Las reglas de las Torres de Hanói son las siguientes:
- Sólo se puede mover un disco cada vez.
- Un disco de mayor tamaño no puede descansar sobre uno más pequeño que él mismo.
- Sólo puedes desplazar el disco que se encuentre arriba en cada varilla.


Aqui podemos ver un ejemplo de como seria la resolución del juego con 3 discos:



Habiendo entendido las reglas de este juego y su funcionamiento nuestro desafío es resolverlo, y para eso utilizaremos lo aprendido de recursividad. A continuación el código que lo resuelve


Podemos observar el resultado de la ejecución con 3 Discos, el cual podemos seguir los pasos que nos indica y resolverlo con, por ejemplo, monedas que tengamos a nuestro alcance, las mismas deben tener 3 tamaños distintos, ser apiladas de mayor a menor, seguir los pasos y habremos resuelto las Torres de Hanói utilizando Recursividad


Esto es todo por hoy, cualquier duda/pregunta en los comentarios :)

Saludos!

-----
Argies_Dario


Compilado con: Dev-Cpp
Sistema Operativo: Windows 7

Fuentes:
Torres de Hanói

No hay comentarios:

Publicar un comentario

Dejanos tu comentario sobre esta nota