¿Cuál es la profundidad de recursión máxima y cómo aumentarla?

Question 1

Tengo esta función recursiva de cola aquí:

def recursive_function(n, sum):
    if n < 1:
        return sum
    else:
        return recursive_function(n-1, sum+n)

c = 998
print(recursive_function(c, 0))

funciona hasta n=997entonces simplemente se rompe y escupe un RecursionError: maximum recursion depth exceeded in comparison. ¿Es esto solo un desbordamiento de pila? ¿Hay alguna forma de evitarlo?

Question 2

Es una protección contra un desbordamiento de pila, sí. Python (o más bien, la implementación de CPython) no optimiza la recursividad final, y la recursividad desenfrenada provoca desbordamientos de pila. Puede comprobar el límite de recurrencia con sys.getrecursionlimit:

import sys
print(sys.getrecursionlimit())

y cambiar el límite de recurrencia con sys.setrecursionlimit:

sys.setrecursionlimit(1500)

pero hacerlo es peligroso: el límite estándar es un poco conservador, pero los stackframes de Python pueden ser bastante grandes.

Python no es un lenguaje funcional y la recursión de cola no es una técnica particularmente eficiente. Reescribir el algoritmo iterativamente, si es posible, generalmente es una mejor idea.

Question 3

Parece que solo necesitas establecer una mayor profundidad de recursión:

import sys
sys.setrecursionlimit(1500)

Question 4

Si a menudo necesita cambiar el límite de recurrencia (por ejemplo, al resolver problemas de programación), puede definir un simple administrador de contexto como esto:

import sys

class recursionlimit:
    def __init__(self, limit):
        self.limit = limit

    def __enter__(self):
        self.old_limit = sys.getrecursionlimit()
        sys.setrecursionlimit(self.limit)

    def __exit__(self, type, value, tb):
        sys.setrecursionlimit(self.old_limit)

Luego, para llamar a una función con un límite personalizado, puede hacer:

with recursionlimit(1500):
    print(fib(1000, 0))

A la salida del cuerpo del with instrucción, el límite de recurrencia se restaurará al valor predeterminado.

PD: es posible que también desee aumentar el tamaño de la pila del proceso de Python para valores grandes del límite de recurrencia. Eso se puede hacer a través de la ulimit shell incorporado o limits.conf(5) archivo, por ejemplo.

Question 5

Es para evitar un desbordamiento de pila. El intérprete de Python limita la profundidad de la recursividad para ayudarlo a evitar recurrencias infinitas, lo que resulta en desbordamientos de pila. Intente aumentar el límite de recurrencia (sys.setrecursionlimit) o reescribiendo su código sin recursividad.

Desde el Documentación de Python:

sys.getrecursionlimit()

Devuelve el valor actual del límite de recurrencia, la profundidad máxima de la pila del intérprete de Python. Este límite evita que la recurrencia infinita provoque un desbordamiento de la pila C y bloquee Python. Se puede establecer por setrecursionlimit().

Question 6

resource.setrlimit también debe usarse para aumentar el tamaño de la pila y evitar fallas de segmento

El núcleo de Linux limita la pila de procesos.

Python almacena variables locales en la pila del intérprete, por lo que la recursividad ocupa espacio en la pila del intérprete.

Si el intérprete de Python intenta sobrepasar el límite de la pila, el kernel de Linux lo convierte en un error de segmentación.

El tamaño límite de la pila se controla con el getrlimit y setrlimit llamadas del sistema.

Python ofrece acceso a esas llamadas al sistema a través del resource módulo.

sys.setrecursionlimit mencionado, por ejemplo, en https://stackoverflow.com/a/3323013/895245 solo aumenta el límite que el propio intérprete de Python impone sobre su propio tamaño de pila, pero no toca el límite impuesto por el kernel de Linux en el proceso de Python.

Programa de ejemplo:

principal.py

import resource
import sys

print resource.getrlimit(resource.RLIMIT_STACK)
print sys.getrecursionlimit()
print

# Will segfault without this line.
resource.setrlimit(resource.RLIMIT_STACK, [0x10000000, resource.RLIM_INFINITY])
sys.setrecursionlimit(0x100000)

def f(i):
    print i
    sys.stdout.flush()
    f(i + 1)
f(0)

Por supuesto, si sigue aumentando setrlimitsu RAM eventualmente se agotará, lo que ralentizará su computadora debido a la locura de intercambio, o matará a Python a través del OOM Killer.

Desde bash, puede ver y establecer el límite de pila (en kb) con:

ulimit -s
ulimit -s 10000

El valor predeterminado para mí es 8Mb.

Ver también:

Configuración del tamaño de pila en un script de python
¿Cuál es el límite estricto de recursividad para Linux, Mac y Windows?

Probado en Ubuntu 16.10, Python 2.7.12.

Question 7

Utilice un lenguaje que garantice la optimización de la cola de llamadas. O usa la iteración. Alternativamente, ponte lindo con decoradores.

Question 8

Me doy cuenta de que esta es una pregunta antigua, pero para aquellos que leen, recomendaría no usar la recursividad para problemas como este: las listas son mucho más rápidas y evitan la recursividad por completo. Yo implementaría esto como:

def fibonacci(n):
    f = [0,1,1]
    for i in xrange(3,n):
        f.append(f[i-1] + f[i-2])
    return 'The %.0fth fibonacci number is: %.0f' % (n,f[-1])

(Use n+1 en xrange si comienza a contar su secuencia de Fibonacci desde 0 en lugar de 1).

¿Ha sido útil esta solución?