Recursividad de Python

Recursividad de Python

En este tutorial, aprenderá a crear una función recursiva (una función que se llama a sí misma).

¿Qué es la recursividad?

La recursividad es el proceso de definir algo en términos de sí mismo.

Un ejemplo del 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 el 1 hasta ese número. Por ejemplo, el factorial de 6 (¡indicado 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 = 3
print("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 llama a sí misma.

Cuando llamamos a esta función con un entero positivo, se llamará recursivamente a sí misma disminuyendo el número.

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 3
3 * factorial(2)      # 2nd call with 2
3 * 2 * factorial(1)  # 3rd call with 1
3 * 2 * 1             # return from 3rd call as number=1
3 * 2                 # return from 2nd call
6                     # return from 1st call

Veamos una imagen que muestra un proceso paso a paso de lo que está pasando:

Nuestra recursividad finaliza cuando el número se reduce a 1. Esto se denomina condición base.

Cada función recursiva debe tener una condición base que detenga la recursividad o, de lo contrario, la función se llama a sí misma infinitamente.

El intérprete de Python limita la profundidad de la recursividad para ayudar a evitar recurrencias infinitas, lo que resulta en desbordamientos de pila.

De forma predeterminada, la profundidad máxima de recursividad 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
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

Ventajas de la recursividad

1. Las funciones recursivas hacen que el código se vea limpio y elegante.
2. Una tarea compleja se puede descomponer en subproblemas más simples mediante la recursividad.
3. La generación de secuencias es más fácil con la recursividad que con alguna iteración anidada.

Desventajas de la recursividad

1. A veces, la lógica detrás de la recursividad es difícil de seguir.
2. Las llamadas recursivas son costosas (ineficientes) ya que ocupan mucha memoria y tiempo.
3. Las funciones recursivas son difíciles de depurar.