¿Qué es la recursión?
La recursividad es el proceso de definir algo en términos de sí mismo.
Un ejemplo de mundo físico sería colocar dos espejos paralelos uno frente al otro. Cualquier objeto entre ellos se reflejaría recursivamente.
Función recursiva de Python
En Python, sabemos que una función puede llamar a otras funciones. Incluso es posible que la función se llame a sí misma. Estos tipos de construcción se denominan funciones recursivas.
La siguiente imagen muestra el funcionamiento de una función recursiva llamada recurse.
el Siguiente es un ejemplo de una función recursiva para encontrar el factorial de un número entero.
El factorial de un número es el producto de todos los enteros desde 1 hasta ese número. Por ejemplo, el factorial de 6 (denotado como 6!) es 1*2*3*4*5*6 = 720.
Ejemplo de una función recursiva
def factorial(x): """This is a recursive function to find the factorial of an integer""" if x == 1: return 1 else: return (x * factorial(x-1))num = 3print("The factorial of", num, "is", factorial(num))Salida
The factorial of 3 is 6
En el ejemplo anterior, factorial() es una función recursiva, como se denomina a sí mismo.
Cuando llamamos a esta función con un número entero positivo, se llama recursivamente a sí mismo por la disminución de la cantidad.
Cada función multiplica el número con el factorial del número debajo de él hasta que es igual a uno. Esta llamada recursiva se puede explicar en los siguientes pasos.
factorial(3) # 1st call with 33 * factorial(2) # 2nd call with 23 * 2 * factorial(1) # 3rd call with 13 * 2 * 1 # return from 3rd call as number=13 * 2 # return from 2nd call6 # return from 1st call
Veamos una imagen que muestra un proceso paso a paso de lo que está sucediendo:
Nuestra recursión termina cuando el número se reduce a 1. Esto se denomina condición básica.
Cada función recursiva debe tener una condición base que detenga la recursión o de lo contrario la función se llama a sí misma infinitamente.
El intérprete de Python limita las profundidades de recursión para ayudar a evitar recursiones infinitas, lo que resulta en desbordamientos de pila.
De forma predeterminada, la profundidad máxima de recursión es 1000. Si se cruza el límite, resulta en RecursionError. Veamos una de esas condiciones.
def recursor(): recursor()recursor()Salida
Traceback (most recent call last): File "<string>", line 3, in <module> File "<string>", line 2, in a File "<string>", line 2, in a File "<string>", line 2, in a RecursionError: maximum recursion depth exceeded
Las ventajas de la recursividad
- Las funciones recursivas hacen que el código se vea limpio y elegante.
- Una tarea compleja se puede dividir en subproblemas más simples utilizando la recursividad.
- La generación de secuencias es más fácil con recursión que con alguna iteración anidada.
Desventajas de la recursión
- A veces la lógica detrás de la recursión es difícil de seguir.
- Las llamadas recursivas son caras (ineficientes), ya que consumen mucha memoria y tiempo.
- Las funciones recursivas son difíciles de depurar.