¿Qué es la función recursiva?
La función se llama a sí misma una y otra vez hasta que satisface una condición recursiva. Una función de recursión divide el problema en problemas más pequeños y llama a su propia lógica para resolver el problema más pequeño. Esta técnica se conoce como divide y vencerás. Se usa en matemáticas y en el campo de la informática.
La función recursiva incluye un caso base (o caso terminal) y un caso recursivo. En el caso base, puede considerar el problema principal a resolver y el caso recursivo divide el problema en partes más pequeñas hasta que alcanza un nivel en el que puede resolverse fácilmente. Un caso recursivo puede devolver un resultado o puede llamarse nuevamente para dividir aún más el problema. Cada vez que el problema se descompone en un problema menor, la función que se llama de forma recursiva guarda el estado de la llamada y espera el resultado de sí misma después de desglosar el problema.
Función recursiva en Python
El concepto de recursión sigue siendo el mismo en Python. La función se llama a sí misma para descomponer el problema en problemas más pequeños. El ejemplo más simple que podríamos pensar en la recursión sería encontrar el factorial de un número.
¡Digamos que necesitamos encontrar el factorial del número 5 => 5! (Nuestro problema)
Para encontrar 5! ¡El problema puede dividirse en pequeños 5! => 5 x 4!
Entonces, para obtener 5! ¡Necesitamos encontrar 4! y multiplícalo por 5.
Sigamos dividiendo el problema
5! = 4! x 5
4! = 3! x 4
3! = 3 x 2!
2! = 2 x 1!
1! = 1
Cuando alcanza el fragmento más pequeño, es decir, obteniendo el factorial de 1, podemos devolver el resultado como
Tomemos un ejemplo de pseudocódigo: -
Algoritmo para factorial
Veamos el algoritmo para factorial:
function get_factorial( n ):
if n < 2:
return 1
else:
return get_factorial(n -1)
Llamadas a funciones
Supongamos que estamos encontrando un factorial de 5.
get_factorial(5) 5 * get_factorial(4) = returns 120 #1st call
get_factorial(4) 4 * get_factorial(3) = returns 24 #2nd call
get_factorial(3) 3 * get_factorial(2) = returns 6 #3rd call
get_factorial(2) 2 * get_factorial(1) = returns 2 #4th call
get_factorial(1) returns 1 #5th call
El resultado final será 120 donde comenzamos la ejecución de la función. Nuestra función de recursión se detendrá cuando el número sea tan reducido que se pueda obtener el resultado.
- La primera llamada que obtiene el factorial de 5 dará como resultado una condición recursiva donde se agregará a la pila y se realizará otra llamada después de reducir el número a 4.
- Esta recursión seguirá llamando y dividiendo el problema en trozos más pequeños hasta que alcance la condición base.
- La condición básica aquí es cuando el número es 1.
- Cada función recursiva tiene su propia condición recursiva y una condición base.
Pros y contras de la función recursiva de Python
- La ejecución de la recursión es para que no haga ningún cálculo hasta que alcance la condición base.
- Al alcanzar las condiciones básicas, puede quedarse sin memoria.
- En un gran problema donde puede haber un millón de pasos o podemos decir que un millón de recursiones para hacer el programa podría terminar dando un error de memoria o una falla de segmentación.
- 1000000! = 1000000 * 999999! =?
- La recursión es diferente a la iteración, no se escala como un método iterativo.
- Diferentes idiomas tienen diferentes optimizaciones para la recursividad.
- En muchos idiomas, el método iterativo funcionaría mejor que la recursividad.
- Cada idioma tiene algunas restricciones sobre la profundidad de la recursión que puede enfrentar al resolver problemas grandes.
- A veces es difícil entender los problemas complejos con la recursividad, mientras que es bastante simple con la iteración.
Algunos profesionales
- En algunos casos, la recursividad es una forma conveniente y más rápida de usar.
- Muy útil en el recorrido del árbol y la búsqueda binaria.
Código de Python - Recursión vs iteración
Entendimos qué es la recursividad y cómo funciona en Python, ya que sabemos que todos los lenguajes tienen una implementación diferente de recursividad para la memoria y las optimizaciones computacionales. Puede haber un caso en el que la iteración sea más rápida que la recursividad.
Aquí compararíamos tanto el método de recursión como el de iteración para ver cómo funciona Python en ambos casos.
1. Código de recursión para factorial
def get_recursive_factorial(n):
if n < 0:
return -1
elif n < 2: #base condition
return 1
else:
return n * get_recursive_factorial(n -1) #recursion condition
2. Problema factorial al usar iteración (bucle)
def get_iterative_factorial(n):
if n < 0:
return -1
else:
fact = 1
for i in range( 1, n+1 ):
fact *= i
return fact
3. Resultados de la impresión
print(get_recursive_factorial(6))
print(get_iterative_factorial(6))
Salida:
Como podemos ver, ambos dan la misma salida que hemos escrito la misma lógica. Aquí no podemos ver ninguna diferencia en la ejecución.
Agreguemos un código de tiempo para obtener más información sobre la ejecución de recursión e iteración en Python.
Importaremos la biblioteca de "tiempo" y verificaremos qué tiempo toma la recursión y la iteración para devolver el resultado.
4. Código con cálculo de tiempo
import time
def get_recursive_factorial(n):
if n < 0:
return -1
elif n < 2:
return 1
else:
return n * get_recursive_factorial(n-1)
def get_iterative_factorial(n):
if n < 0 :
return -1
else:
fact = 1
for i in range(1, n+1):
fact *= i
return fact
start_time = time.time()
get_recursive_factorial(100)
print("Recursion--- %s seconds ---" % (time.time() - start_time))
start_time = time.time()
get_iterative_factorial(100)
print("Iteration--- %s seconds ---" % (time.time() - start_time))
Haremos repetidas ejecuciones con un valor diferente para factorial y veremos los resultados. Los siguientes resultados pueden variar de máquina a máquina. Hemos utilizado MacBook Pro 16 GB de RAM i7.
Estamos usando Python 3.7 para la ejecución
Caso 1: - Factorial de 6:
Caso 2: Factorial de 50:
Caso 3: Factorial de 100:
Caso 4: Factorial de 500:
Caso 5: Factorial de 1000:
Hemos analizado ambos métodos en un problema diferente. Además, ambos han tenido un desempeño similar, excepto el caso 4.
En el caso 5, recibimos un error al hacerlo con recursividad.
Python tiene una restricción en la profundidad máxima que puede alcanzar con la recursión, pero el mismo problema que pude resolver con iteración.
Python tiene restricciones contra el problema del desbordamiento. Python no está optimizado para la recursión de cola, y la recursión no controlada provoca un desbordamiento de la pila.
La función "sys.getrecursionlimit ()" le indicaría el límite de recursión.
El límite de recursión se puede cambiar, pero no se recomienda que pueda ser peligroso.
Conclusión: función recursiva de Python
- La recursión es una solución útil para algunos problemas como el recorrido del árbol y otros problemas.
- Python no es un lenguaje de programación funcional y podemos ver que la pila de recursión no está tan optimizada en comparación con la iteración.
- Deberíamos usar la iteración en nuestro algoritmo ya que está más optimizado en Python y le brinda una mejor velocidad.
Artículos recomendados
Esta es una guía de la función recursiva en Python. Aquí discutimos qué es la función recursiva, la función recursiva en Python, el algoritmo para factorial, etc. También puede consultar nuestros otros artículos sugeridos para obtener más información:
- Factorial en Python
- Comandos de Spark Shell
- Mejores compiladores de C
- Tipos de algoritmos
- Programa Factorial en JavaScript
- Guía de la lista de comandos de shell de Unix
- Tipos de formularios en reacción con ejemplos