Python | Límite de recurrencia de manejo

Cuando ejecuta una función recursiva en Python en una entrada grande (> 10 ^ 4), es posible que encuentre un «error de profundidad máxima de recursión excedida». Este es un error común cuando se ejecutan algoritmos como DFS, factorial, etc. en entradas grandes. Esto también es común en la programación competitiva en múltiples plataformas cuando intenta ejecutar un algoritmo recursivo en varios casos de prueba. 
En este artículo, veremos por qué ocurre este error y cómo manejarlo en Python. Para entender esto, primero debemos observar la recursividad de la cola.
recursividad de cola –
En una función recursiva típica, generalmente hacemos las llamadas recursivas primero y luego tomamos el valor de retorno de la llamada recursiva para calcular el resultado. Por lo tanto, solo obtenemos el resultado final después de que todas las llamadas recursivas hayan devuelto algún valor. Pero en una función recursiva de cola, los diversos cálculos y declaraciones se realizan primero y la llamada recursiva a la función se realiza después de eso. Al hacer esto, pasamos los resultados del paso actual a la siguiente llamada recursiva a la función. Por lo tanto, la última declaración en una función recursiva Tail es la llamada recursiva a la función. 
Esto significa que cuando realizamos la siguiente llamada recursiva a la función, el marco de pila actual (ocupado por la llamada de función actual) ya no es necesario. Esto nos permite optimizar el código. Simplemente reutilizamos el marco de pila actual para el siguiente paso recursivo y repetimos este proceso para todas las demás llamadas a funciones.
Usando la recursividad regular, cada llamada recursiva empuja otra entrada a la pila de llamadas. Cuando las funciones regresan, se extraen de la pila. En el caso de la recursión de cola, podemos optimizarla para que solo se use una entrada de pila para todas las llamadas recursivas de la función. Esto significa que incluso en entradas grandes, no puede haber desbordamiento de pila. Esto se llama optimización de recursión de cola.
Los lenguajes como lisp y c/c++ tienen este tipo de optimización. Pero, el intérprete de Python no realiza la optimización de recurrencia de cola. Debido a esto, el límite de recurrencia de python generalmente se establece en un valor pequeño (aproximadamente, 10 ^ 4). Esto significa que cuando proporcione una entrada grande a la función recursiva, obtendrá un error. Esto se hace para evitar un desbordamiento de pila. El intérprete de Python limita el límite de recurrencia para evitar recurrencias infinitas. 
  
Manejo del límite de
recurrencia: el módulo «sys» en Python proporciona una función llamada setrecursionlimit()para modificar el límite de recurrencia en Python. Toma un parámetro, el valor del nuevo límite de recurrencia. Por defecto, este valor suele ser 10^3. Si está tratando con entradas grandes, puede configurarlo en 10 ^ 6 para que las entradas grandes se puedan manejar sin errores.
Ejemplo:
Considere un programa para calcular el factorial de un número usando recursividad. Cuando se le da una entrada grande, el programa falla y da un «error de profundidad de recursión máxima excedida».
 

# A simple recursive function
# to compute the factorial of a number
def fact(n):
 
    if(n == 0):
        return 1
 
    return n * fact(n - 1)
 
 
if __name__ == '__main__':
 
    # taking input
    f = int(input('Enter the number: \n'))
 
    print(fact(f))

Producción : 
 

Usando el método setrecursionlimit(), podemos aumentar el límite de recurrencia y el programa puede ejecutarse sin errores incluso con entradas grandes.
 

# importing the sys module
import sys
 
# the setrecursionlimit function is
# used to modify the default recursion
# limit set by python. Using this,
# we can increase the recursion limit
# to satisfy our needs
 
sys.setrecursionlimit(10**6)
 
# a simple recursive function
# to compute the factorial of a number
# it takes one parameter, the
# number whose factorial we
# want to compute and returns
# its factorial
def fact(n):
 
    if(n == 0):
        return 1
 
    return n * fact(n - 1)
 
if __name__ == '__main__':
 
    # taking input
    f = int(input('Enter the number: \n'))
 
    print(fact(f))

Producción :