Básicamente, una función recursiva es una función que se llama a sí misma en el proceso de ejecución. Su funcionamiento es muy similar a la iteraciones que vimos en clase pasadas. Comenzaremos trabajando con el siguiente ejemplo que posteriormente explicaremos paso a paso:
# Cuenta regresiva
def cuentaRegresiva(x):
x -= 1
if x >= 0:
print(x)
cuentaRegresiva(x)
else:
print('Fin')
cuentaRegresiva(4)
3 2 1 0 Fin
donde
x=4 procedemos a quitarle uno y volver a asignar este valor a la variable x, de tal manera x=3, después imprimimos este valor y posteriormente volvemos a aplicar la función cuentaRegresiva(x)x=3ingresa a nuestra función por lo que se le resta uno y se le vuelve a asignar este valor, es así como x=2 y es impreso este valor, luego, nuevamente es ingresado en la función cuentaRegresiva(x).Continuaremos con este procedimiento hasta que x=0 pues, una vez que dicho valor es impreso y es ingresado a la función cuentaRegresiva(x), una vez que le quitemos uno tendremos como resultado x=-1 por lo que pasaremos a la ejecución del código correspondiente al else de nuestro condicional if, lo cual regresa el mensaje 'Fin'.
Podemos ver otro ejemplo sobre funciones recursivas en Python utilizando el factorial de un número. Recordemos que dado $n\in\mathbb{N}$ tenemos que
$$ n!=n(n-1)\cdots3\cdot2\cdot1 $$Ahora, podemos implemenar lo anterior mediante funciones recursivas:
# definimos la función
def factorial(n):
if n == 0 or n == 1:
resultado = 1
elif n > 1:
resultado = n * factorial(n - 1)
return resultado
# probamos nuestra función
factorial(5)
120
donde al ingresar el 5 a la función obtenemos que resultado = 5 * factorial(4), luego al asignarle el 4 a la función tendremos que resultado = 4 * factorial(3) y así hasta obtener que resultado = 2 * factorial(1), donde factorial(1) retorna como resultado 1 y por ende tendremos que
resultado = 5 * 4 * 3 * 2 * 1o lo que es lo mismo obtenemos el valor de resultado final el cual es 120.
Veamos que
factorial(4)
24
también puede explicarse observando que
Para finalizar volvamos a ver la función recursiva que nos arroja el factorial de un número, observando cuidadosamente cada ejecución cuando llamamos a dicha función:
# definimos la función
def factorial(n):
print("Número en ejecución", n)
if n == 0 or n == 1:
resultado = 1
elif n > 1:
resultado = n * factorial(n - 1)
print("Resultado", resultado)
return resultado
# probamos nuestra función
factorial(5)
Número en ejecución 5 Número en ejecución 4 Número en ejecución 3 Número en ejecución 2 Número en ejecución 1 Resultado 2 Resultado 6 Resultado 24 Resultado 120
120
Notemos que primero se imprime el mensaje Número de ejecución 5 y ejecutaremos las líneas de código referentes al elif (es importante recordar que la ejecución en Python es de arriba a abajo línea por línea), sin embargo cuando estemos en la línea de ejecución resultado = n * factorial(n - 1) tendremos que resultado = 5 * factorial(4) y la función factorial() se volvera a llamar por lo que no se ejecutara en ese momento la línea siguiente print("Resultado", resultado). De tal manera, en este bloque tendremos pendiente obtener resultado = 5 * factorial(4).
Una vez pasado al siguiente bloque de ejecución se imprime el mensaje Número de ejecución 4 y tendremos la ejecución de la línea de código resultado = 4 * factorial(3) la cual quedará pendiente y además la función se vuelve a llamar.
Una vez pasado al siguiente bloque de ejecución se imprime el mensaje Número de ejecución 3 y tendremos la ejecución de la línea de código resultado = 3 * factorial(2) la cual quedará pendiente y además la función se vuelve a llamar.
Una vez pasado al siguiente bloque de ejecución se imprime el mensaje Número de ejecución 2 y tendremos la ejecución de la línea de código resultado = 2 * factorial(1) la cual quedará pendiente y además la función se vuelve a llamar.
Continuando con este procedimiento se imprime el mensaje Número de ejecución 1 y en este caso se ejecutará la línea de código dentro de la condición del if, esto es resultado = 1. De ahí pasamos a la línea return resultado lo cual arroja de llamar a la función factorial(1) el valor de 1 por lo dicho anteriormente. Una vez que ya tenemos un resultado fijo se procede a dar el resultado de las operaciones que quedaron pendientes.
De inmediato regresamos a la línea que quedó pendiente de ejecución resultado = 2 * factorial(1) lo cual asigna el valor de 2 en la variable resultado y después se ejecuta la línea inmediata siguiente print("Resultado", 2). Es así como tenemos que, al llamar la función factorial(2), se nos regresa como resultado el valor de 2.
Luego ejecutamos resultado = 3 * factorial(2) el cual asigna el valor de 6 a la variable resultado pues factorial(2) arroja el valor de 2. Después se imprime print("Resultado", 6). Y así sucesivamente.
Finalmente vamos a crear un función recursiva para calcular los números de fibonacci. Recordemos que el n-ésimo número de Fibonacci se obtiene a partir de los dos anteriores, esto es:
$$ F_{n}=F_{n-1}+F_{n-2}, \ \ \ n \geq 2 $$Por ejemplo, tomando los primeros dos números de la sucesión de Fibonacci $1$ y $1$ podemos obtener el tercer término el cual es $1+1=2$, el cuarto término el cual es $1+2=3$, el quinto término el cual es $2+3=5$, etcétera.
Lo que haremos será que nuestra función devuelva 1 cuando el término a buscar ($n$) sea 1 ó 2 y en los demás casos devolverá el valor de fibonacci(n-1) + fibonacci(n-2). Por ejemplo, si $n=4$ entonces la función devolverá el valor de fibonacci(3) + fibonacci(2) que es lo mismo que fibonacci(3) + 1. Luego, para obtener fibonacci(3) se tedrá que la función devolverá el valor de resultante de fibonacci(2) + fibonacci(1) lo cual equivale a $1+1=2$ y por ende, regresando a la ejecución pendiente fibonacci(3) + fibonacci(2) tendremos el valor de $2+1=3$. Lo anterior se puede implementar en código como sigue:
# Definimos la función
def fibonacci(n):
if n == 1:
# el primer término de la sucesión es el 1
return n
elif n == 2:
# el segundo término de la sucesión es el 1
return n - 1
return fibonacci(n-1) + fibonacci(n-2)
# probamos nuestra función
for i in range(1,7):
print(f'El término {i} de la sucesión es: {fibonacci(i)}')
El término 1 de la sucesión es: 1 El término 2 de la sucesión es: 1 El término 3 de la sucesión es: 2 El término 4 de la sucesión es: 3 El término 5 de la sucesión es: 5 El término 6 de la sucesión es: 8
