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

recursive loop python

Question

Tengo esta función recursiva cola aquí:

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

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

Funciona hasta n = 997, luego se rompe y escupe una "profundidad máxima de recursión superada en comparación" RuntimeError . ¿Esto es sólo un desbordamiento de pila? ¿Hay alguna manera de evitarlo?

Answer 1

¿Usar generadores?

def fib():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

fibs = fib() #seems to be the only way to get the following line to work is to
             #assign the infinite generator to a variable

f = [fibs.next() for x in xrange(1001)]

for num in f:
        print num

La función fib () anterior se adaptó de: http://intermediatepythonista.com/python-generators

Answer 2

Como suggested @alex, podría usar una función de generador para hacer esto. Aquí está el equivalente del código en su pregunta:

def fib(n):
    def fibseq(n):
        """ Iteratively return the first n Fibonacci numbers, starting from 0 """
        a, b = 0, 1
        for _ in xrange(n):
            yield a
            a, b = b, a + b

    return sum(v for v in fibseq(n))

print format(fib(100000), '',d'')  # -> no recursion depth error

Answer 3

Es para evitar un desbordamiento de pila. El intérprete de Python limita la profundidad de la recursión para ayudarte a evitar las recursiones infinitas, lo que resulta en desbordamientos de pila. Intente aumentar el límite de recursión (sys.setrecursionlimit) o ​​volver a escribir su código sin recursión.

del sitio web de python :

sys.getrecursionlimit()

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

Answer 4

Es un protector contra un desbordamiento de pila, sí. Python (o más bien, la implementación de CPython) no optimiza la recursión de cola, y la recursión desenfrenada provoca desbordamientos de pila. Puede cambiar el límite de recursión con sys.setrecursionlimit , pero hacerlo es peligroso. El límite estándar es un poco conservador, pero los cuadros de pila de Python pueden ser bastante grandes.

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

Answer 5

Me doy cuenta de que esta es una pregunta antigua, pero para quienes la lean, recomendaría no usar la recursión para problemas como este: las listas son mucho más rápidas y evitan la recursión 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 de 0 en lugar de 1.)

Answer 6

Muchos recomiendan que aumentar el límite de recursión es una buena solución, pero no lo es porque siempre habrá un límite. En su lugar, utilice una solución iterativa.

def fib(n):
    a,b = 1,1
    for i in range(n-1):
        a,b = b,a+b
    return a
print fib(5)

Answer 7

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

sys.setrecursionlimit(1500)

Answer 8

Por supuesto, los números de Fibonacci se pueden calcular en O (n) aplicando la fórmula de Binet:

from math import floor, sqrt

def fib(n):                                                     
    return int(floor(((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5))+0.5))

Como señalan los comentaristas, no es O (1) sino O (n) debido a 2**n . También una diferencia es que solo obtiene un valor, mientras que con la recursión obtiene todos los valores de Fibonacci(n) hasta ese valor.

Answer 9

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

import sys

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

    def __enter__(self):
        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))

Al salir del cuerpo de la instrucción with , el límite de recursión se restaurará al valor predeterminado.

Answer 10

Si desea obtener solo unos pocos números de Fibonacci, puede utilizar el método de matriz.

from numpy import matrix

def fib(n):
    return (matrix(''0 1; 1 1'', dtype=''object'') ** n).item(1)

Es rápido ya que numpy usa un algoritmo de exponenciación rápida. Obtienes respuesta en O (log n). Y es mejor que la fórmula de Binet porque usa solo números enteros. Pero si desea que todos los números de Fibonacci lleguen a n, entonces es mejor hacerlo por memorización.

Answer 11

Tuve un problema similar con el error "Profundidad de recursión máx. Excedida". Descubrí que el error estaba siendo provocado por un archivo dañado en el directorio que estaba haciendo un bucle con os.walk. Si tiene problemas para resolver este problema y está trabajando con rutas de archivos, asegúrese de limitarlo, ya que podría ser un archivo dañado.

Answer 12

Utilice un lenguaje que garantice la optimización de llamadas de cola. O utilizar la iteración. Alternativamente, conseguir lindo con decorators .

Answer 13

También se debe usar resource.setrlimit para aumentar el tamaño de la pila y evitar segfault

El kernel de Linux limita la pila de procesos.

Python almacena las variables locales en la pila del intérprete, por lo que la recursión ocupa el espacio de pila del intérprete.

Si el intérprete de Python intenta sobrepasar el límite de pila, el kernel de Linux lo segrega.

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

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

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 sigues incrementando ulimit, tu RAM se agotará, lo que frenará tu computadora hasta detenerse debido a un cambio de locura 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:

• Estableciendo stacksize en un script de python
• Python: ¿Cuál es el límite de recursión para Linux, Mac y Windows?

Probado en Ubuntu 16.10, Python 2.7.12.