Tutorial de Python - Función recursiva

1. Qué es la función recursiva de Python
2. Limitación de la recursividad
3. Ventaja de la recursividad
4. Desventaja de la Recursividad

En esta sección, aprenderá la función recursiva de Python.

Qué es la función recursiva de Python

Una función recursiva es una función que se llama a sí misma y este proceso se llama recursividad de la función.

Por ejemplo, vamos a calcular el factorial de un número, por ejemplo, 6.

6 * 5 * 4 * 3 * 2 * 1

En el siguiente código, se crea una función recursiva que encuentra el factorial de un número:

def fact(n):
    """Recursive function to find factorial"""
    if n == 1:
        return 1
    else:
        return n * fact(n - 1)


a = 6
print("Factorial of", a, "=", fact(a))

Factorial of 6 = 720

La función fact(n) es una función recursiva. La función fact se llama a sí misma con el argumento n-1 hasta que el número se convierte en 1 y así es como se calcula el factorial, es decir, multiplicando el número por el factorial de uno menos que el número.

En esta función recursiva, hay una condición base que es cuando el número se convierte en 1, 1 se devuelve y de esta manera la llamada recursiva se vuelve finita.

Cuando se crea una función recursiva, debe haber una condición base para terminar esa llamada recursiva.

Limitación de la recursividad

Como ha notado, cada vez que la función se llama a sí misma, necesita algo de memoria para almacenar algunos valores intermedios. Por lo tanto, la función recursiva consume mucha más memoria que una función normal no recursiva. Python establece la limitación de llamadas de recursividad en 3000.

>>> import sys
>>> sys.getrecursionlimit()
3000

Aumenta un RecursionError si la recursividad excede los 3000.

def fact(n):
    """Recursive function to find factorial"""
    if n == 1:
        return 1
    else:
        return n * fact(n - 1)


print(fact(4000))

Traceback (most recent call last):
  File "<pyshell#2>", line 1, in <module>
    print(factorial(4000))
  File "<pyshell#1>", line 5, in factorial
    return n * factorial(n-1)
  File "<pyshell#1>", line 5, in factorial
    return n * factorial(n-1)
  File "<pyshell#1>", line 5, in factorial
    return n * factorial(n-1)
  [Previous line repeated 989 more times]
  File "<pyshell#1>", line 2, in factorial
    if n == 1:
RecursionError: maximum recursion depth exceeded in comparison

Solución para eliminar la limitación de la recursividad

Puede resolver la limitación de recursividad estableciendo la limitación de recursividad en un número mayor que la recursividad requerida.

import sys

sys.setrecursionlimit(5000)


def fact(n):
    """Recursive function to find factorial"""
    if n == 1:
        return 1
    else:
        return n * fact(n - 1)


print(fact(4000))

Ventaja de la recursividad

• Usando funciones recursivas, el problema puede ser dividido en sub-problemas que pueden ser resueltos fácilmente.
• El código se vuelve limpio y ordenado.

Desventaja de la Recursividad

• A veces es difícil seguir la lógica de la función recursiva.
• Resolver cada sub-problema llevará mucho tiempo, por lo que las funciones recursivas son ineficientes.