Entender la Recursividad

¿Qué eso de recursividad?, probablemente los que no estéis muy familiarizados con la programación puede que sea un concepto que no os suene o que conozcáis desde la parte de las matemáticas, pero la recursividad es una de las herramientas más potentes e importantes en Computación.

El concepto no se limita solo al ámbito de la programación si no que se encuentra presenta en la propia naturaleza.

En este articulo voy a explicaros este concepto de una manera sencilla usando Python, algunas funciones matemáticas y por supuesto el famoso juego de las Torres de Hanoi. El objetivo es que se entienda la diferencia de cuando programamos una función usando la recursividad, y cuando no la usamos. La capacidad de computación que ganamos cuando somos capaces de controlar y aplicar este concepto de forma correcta.

Antes de empezar debemos definir que es Recursividad

Una función es recursiva cuando se define en términos de si misma

Y como ejemplo vamos a usar una de las funciones que muestra perfectamente este concepto, la función factorial.

Factorial

$f(x)=x!$

$n!= n * n(n-1) * ..... * 3 * 2 * 1$

$5! = 5.4.3.2.1$

Esta función se puede expresar también como una función recursiva

* $f(x) = x * f(x-1)!$

Ahora vamos a realizar esta actividad con Python, creando la función sin usar recursividad y usando recursividad. Mirar el video

Potencias

Se llama función portencia a cualquier expresión que se puede escribir de la forma:

$f(x)=x^a$ Siendo a cualquier número real

Si lo expresamos de forma de productto tenemos

$a^n=\prod^n_{i=1}a_i$
$a^n=a * a^{n-1}$ (Función recursiva)

Ahora que ya hemos entendido como se puede expresar una potencia, debemos realizar una función en Python a la cual le pase dos parámetros (x,y), uno de ellos es la base y el otro el exponente. La función me debe devolver el resultado de esa potencia. Mirar el video

Serie de Fibonacci

Vamos a trabajar con la famosa serie de Fibonacci. Debéis recordar que la serie de Fibonacci es muy sencilla de aplicar.
Se representa como: $f_n=f_{n-1}+f_{n-2}$ .
Consiste en sumar en una sucesión de números que comienza con 0 y 1. Sumar los dos números anteriores para hallar el tercero. Es decir:

0+1= 1
1+1=2
1+2=3
2+3=5
3+5=8

Debemos realizar una función en Python a la cual le pase un único parametro (n), la posición en la serie de Fibonacci. La función me debe devolver el número en la posición n. Mirar el video

Las torres de Hanoi

Se conoce como un juego matemático inventado por el francés Édouard Lucas en 1883. Consiste en pasar n discos apilados y ordenados por tamaño de una estaca a otra, utilizando una estaca auxiliar si fuera necesario.

Siguiendo unas simples reglas

Un disco de radio R nunca se ponga encima de otro de radio r (asumiendo que R>r)
Solo es posible mover un disco a la vez y siempre el disco en el tope de la pila

¿Cuál es el menor número de movimientos para pasar 3 discos?
Inténtalo en: https://www.geogebra.org/m/NqyWJVra

Hay un algoritmo que me resuelva el juego para n discos
¿Qué ocurre cuando el número de discos es muy alto?
¿Puedo saber el número mínimo de movimientos?
¿Cuanto puedes tardar?

Vamos a entenderlo y resolverlo!!

Lo primero que debemos entender es que para resolver el juego hay un patrón que debemos reconocer:

Llamemos a las Torres
A (origen)
B (destino)
Aux (auxiliar)

Llamemos a los discos
De 1 a n, siendo n el disco más grande

¿Algoritmo? . Mira los movimientos que siempre se repiten

Un ejemplo con 3 discos

1A ==> 1B (el disco 1 de Torre Origen a Torre Destino)
2A ==> 2Aux (el disco 2 de Torre Origen a Torre Auxiliar)
1B ==> 1Aux (el disco 1 de Torre Destino a Torre Auxiliar)

3A ==> 3B (el disco 3 de Torre Origen a Torre Destino)

1Aux ==> 1A (el disco 1 de Torre Auxliar a Torre Origen)
2Aux ==> 2B (el disco 2 de Torre Auxiliar a Torre Destino)
1A ==> 1B (el disco 1 de Torre Origen a Torre Destino)

No hemos dado cuenta que siempre todos los discos excepto la base, es decir n-1 deben pasar por la torre auxiliar para depués mover la base al destino y nuevamente mover los n-1 discos al destino, YA TENEMOS la RECURSIVIDAD. Vamos hacer el código en Python, mira el video