Referencia: Rodríguez 6.0 p168
Una función recursiva muy conocida y definida en la matemática es el factorial. El factorial tiene la característica que se puede llamar a si misma.
5! = 5x4!
4! = 4x3!
3! = 3x2!
2! = 2x1!
por definición 1! = 1
Se interpreta que para encontrar 5! requerimos la respuesta de 4!.
Para encontrar 4! se debe calcular 3! y así sucesivamente,
hasta llegar al valor inicial de la función que es 1!=1
La solución se interpreta hacia atrás, empezando desde la respuesta conocida de 1! =1 y reemplazando los valores en las operaciones que esperaban por resolver:
5! = 5x4! = 5x24 = 120
4! = 4x3! = 4x6 = 24
3! = 3x2! = 3x2 = 6
2! = 2x1! = 2x1 =2
por definición 1! = 1
Observamos que la función recursiva tiene: valores iniciales, que se llama a si misma, y de forma matemática tiene una forma elegante de escribirse:
n! = \begin{cases} 1 && n=1 \\ n(n-1)! && n>1\end{cases}Escribir la función recursiva en un algoritmo consiste en transcribir paso a paso lo descrito en forma matemática.
# factorial en forma recursiva def factorial(n): if n==1: resultado = 1 if n>1: resultado = n*factorial(n-1) return(resultado)
una vez que se ejecuta el algoritmo para que esté disponible en memoria, se usa llamando a la función
>>> factorial(5) 120 >>> factorial(1) 1 >>> factorial(4) 24 >>>
Existen otras funciones recursivas en matemáticas que se pueden fácilmente convertir a algoritmos como Fibonacci, Padovan, incluso algunas que funcionan en parejas como Par e impar. Se muestran algunas en la sección de ejemplos.
Observaciones de uso
Sin embargo, hay que considerar que la recursividad se usa con precaución, pues las llamadas generan otra instancia que puede saturar la capacidad del computador.
En el ejemplo se observa que se tienen operaciones en espera de resultados de la siguiente respuesta, cada llamada usa memoria, tiempo de cómputo como recursos.
Por ejemplo, al intentar de obtener factorial(1000) en forma recursiva, se obtiene un error "RecursionError: maximum recursion depth exceeded in comparison".
Los lenguajes de programación tienen como límite máximo de llamadas recursivas, para evitar saturar los recursos disponibles de memoria y tiempo computacional.
Ejercicios resueltos
2Eva_IIT2007_T4 Fibonacci recursiva
Solución propuesta: s2Eva_IIT2007_T4 Fibonacci recursiva
2Eva_IT2007_T1 Funciones par e impar recursivas
Solución Propuesta: s2Eva_IT2007_T1 Funciones par e impar recursivas
3Eva_IT2004_T3 Multiplicar con campesino egipcio
Solución Propuesta: s3Eva_IT2004_T3 Multiplicar con campesino egipcio