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

422

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=997, luego simplemente se rompe y escupe a RecursionError: maximum recursion depth exceeded in comparison. ¿Es esto solo un desbordamiento de pila? ¿Hay alguna forma de evitarlo?

quantumSoup
fuente
3
Ver también stackoverflow.com/questions/5061582/…
Thomas Ahle
99
la memorización podría acelerar su función y aumentar su profundidad recursiva efectiva al hacer que los valores calculados previamente terminen en lugar de aumentar el tamaño de la pila.
Cyoce
2
El límite de recursión suele ser 1000.
Boris
1
@tonix el intérprete agrega un marco de pila (las line <n>, in <module>trazas en la pila) y este código toma 2 cuadros de pila n=1(porque el caso base es n < 1, por n=1lo que aún se repite). Y supongo que el límite de recursión no es inclusivo, ya que en "error cuando alcanza 1000" no "error si excede 1000 (1001)". 997 + 2es inferior a 1000, por lo 998 + 2que no funciona porque llega al límite.
Boris
1
@tonix no. recursive_function(997)funciona, se rompe a las 998. Cuando lo llama recursive_function(998), usa 999 marcos de pila y el intérprete agrega 1 marco (porque su código siempre se ejecuta como si fuera parte del módulo de nivel superior), lo que hace que llegue al límite de 1000.
Boris

Respuestas:

469

Es una protección 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 verificar el límite de recursión con sys.getrecursionlimity 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 marcos de pila de Python pueden ser bastante grandes.

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

Thomas Wouters
fuente
44
Según mi experiencia, debe aumentar el límite tanto en el syscomo en los resourcemódulos: stackoverflow.com/a/16248113/205521
Thomas Ahle
3
Como una táctica para convertirlo a una versión iterativa, se podría usar un decorador de optimización de llamada de cola
jfs
3
puede usar svn.python.org/projects/python/trunk/Tools/scripts/… para conocer el límite superior de su sistema operativo
Ullullu
8
Para aquellos interesados ​​en la fuente, el límite de recursión predeterminado se establece en 1000 hg.python.org/cpython/file/tip/Python/ceval.c#l691 y se puede cambiar usando la API en hg.python.org/cpython /file/tip/Python/sysmodule.c#l643 que a su vez establece el límite al nuevo valor en hg.python.org/cpython/file/tip/Python/ceval.c#l703
Pramod
17
La recursividad de la cola es una técnica perfectamente eficiente en un lenguaje de programación optimizado para ello. Para el tipo correcto de problema, puede ser considerablemente más expresivo y una implementación iterativa. La respuesta probablemente significa "en Python específicamente", pero eso no es lo que dice
Peter R
136

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

import sys
sys.setrecursionlimit(1500)
David Young
fuente
En mi caso, olvidé la declaración de devolución en el caso base y superó los 1000. Python comenzó a lanzar esta excepción y me sorprendió, porque estaba seguro del no. de pilas que va a crear para ejecutarlo.
vijayraj34
sys.setrecursionlimit (50) o una pequeña cantidad es útil si su programa está ingresando recursividad y desea que el mensaje de error NO sea páginas y páginas del mismo texto. Encontré esto muy útil al depurar (mi) código recursivo incorrecto.
Peawormsworth
56

Es para evitar un desbordamiento de pila. El intérprete de Python limita las profundidades de recursión para ayudarlo a evitar infinitas recursiones, lo que resulta en desbordamientos de pila. Intenta aumentar el límite de recursión ( sys.setrecursionlimit) o reescribe tu código sin recurrencia.

De la documentación de Python :

sys.getrecursionlimit()

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

Scharron
fuente
En mi Anaconda x64, 3.5 Python en Windows, el límite predeterminado es 1000.
Guillaume Chevalier
30

Si a menudo necesita cambiar el límite de recurrencia (por ejemplo, mientras resuelve acertijos 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 withdeclaración, el límite de recursión se restaurará al valor predeterminado.

Eugene Yarmash
fuente
También desea aumentar el límite de recurrencia del proceso conresource . Sin él, obtendrá una falla de segmentación y todo el proceso de Python se bloqueará si es setrecursionlimitdemasiado alto e intente usar el nuevo límite (aproximadamente 8 megabytes de cuadros de pila, que se traduce en ~ 30,000 cuadros de pila con la función simple anterior, en mi portátil).
Boris
16

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

Marcelo Cantos
fuente
36
Eso es más bien tirar al bebé con el agua del baño.
Russell Borogove
3
@Russell: Solo una de las opciones que ofrecí aconseja esto.
Marcelo Cantos
"Ponerse lindo con los decoradores" no es exactamente una opción.
Sr. B
@ Mr.B a menos que necesite más que ulimit -smarcos de pila, sí, es stackoverflow.com/a/50120316
Boris
14

resource.setrlimit también se debe usar para aumentar el tamaño de la pila y evitar la falla predeterminada

El kernel de Linux limita la pila de procesos .

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

Si el intérprete de Python intenta superar 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 las getrlimity setrlimitllamadas al sistema.

Python ofrece acceso a esas llamadas del sistema a través del resourcemódulo.

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 ulimit, su RAM se agotará, lo que ralentizará su computadora debido a la locura del intercambio o matará a Python a través del OOM Killer.

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

ulimit -s
ulimit -s 10000

El valor predeterminado para mí es 8Mb.

Ver también:

Probado en Ubuntu 16.10, Python 2.7.12.

Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
fuente
1
Intentar establecer rlimit_stackdespués de las correcciones de Choque de pila puede provocar fallas o problemas relacionados. También vea Red Hat Issue 1463241
jww
Usé esto (la parte de recursos de Python) para ayudar a mi implementación del algoritmo de Kosaraju en el conjunto de datos medio (enorme) del profesor Tim Roughgarden. Mi implementación funcionó en conjuntos pequeños, sin duda el problema con un gran conjunto de datos fue el límite de recursión / pila ... ¿O no? ¡Pues sí! ¡Gracias!
nilo
9

Me doy cuenta de que esta es una vieja pregunta, 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 recursión por completo. 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.)

Daniel
fuente
13
¿Por qué usar el espacio O (n) cuando puedes usar O (1)?
Janus Troelsen
11
En caso de que el comentario del espacio O (n) fuera confuso: no use una lista. La lista mantendrá todos los valores cuando todo lo que necesite sea el enésimo valor. Un algoritmo simple sería mantener los dos últimos números de Fibonacci y agregarlos hasta llegar al que necesita. También hay mejores algoritmos.
Milimétrico
3
@Mathime: xrangese llama simplemente range, en Python 3.
Eric O Lebigot
1
@EOL Soy consciente de esto
Mathime
77
@Mathime Estaba haciendo cosas explícitas para aquellos que leen estos comentarios.
Eric O Lebigot
9

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 obtienes un valor, mientras que con la recursividad obtienes todos los valores de Fibonacci(n)hasta ese valor.

rwst
fuente
8
No hay un tamaño máximo de un largo en python.
pppery
8
Vale la pena señalar que esto falla por mayor ndebido a la imprecisión de coma flotante: la diferencia entre (1+sqrt(5))**ny se (1+sqrt(5))**(n+1)convierte en menos de 1 ulp, por lo que comienza a obtener resultados incorrectos.
2
En realidad no hay grandes números enteros en NumPy ...
Eric O Lebigot
@Mego ¿Qué? ¡Es la diferencia entre (1+sqrt(5))**ny ((1+sqrt(5))**n)+1eso se convierte en menos de 1 ulp! (error tipográfico pequeño) Además, {@} rwst ¡Eso no es O (1)! El cálculo 2**nlleva al menos O (n) tiempo.
user202729
3
@ user202729 Eso no es cierto, el cálculo 2**nes efectivamente O (log (n)) usando Exponentiattion mediante cuadratura .
Sam
6

Tuve un problema similar con el error "Profundidad máxima de recursión excedida" Descubrí que el error estaba siendo desencadenado por un archivo corrupto en el directorio con el que estaba pasando os.walk. Si tiene problemas para resolver este problema y está trabajando con rutas de archivos, asegúrese de reducirlo, ya que podría ser un archivo corrupto.

Tyler
fuente
2
El OP da su código, y su experimento es reproducible a voluntad. No involucra archivos corruptos.
T. Verron
55
Tienes razón, pero mi respuesta no está orientada al OP, ya que esto fue hace más de cuatro años. Mi respuesta tiene como objetivo ayudar a aquellos con errores de MRD indirectamente causados ​​por archivos corruptos, ya que este es uno de los primeros resultados de búsqueda. Ayudó a alguien, ya que fue votado. Gracias por el voto negativo.
Tyler
2
Esto fue lo único que encontré en cualquier lugar al buscar mi problema que conectaba un rastreo de "profundidad de recursión máxima" a un archivo dañado. ¡Gracias!
Jeff
5

Si desea obtener solo unos pocos números de Fibonacci, puede usar 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. Obtiene respuesta en O (log n). Y es mejor que la fórmula de Binet porque solo usa números enteros. Pero si desea todos los números de Fibonacci hasta n, entonces es mejor hacerlo memorizando.

bebidek
fuente
Lamentablemente, no puedes usar numpy en la mayoría de los jueces de programación competitivos. Pero sí señor, su solución es mi favorita. He usado la solución de matriz para algunos problemas. Es la mejor solución cuando necesita un número de Fibonacci muy grande y no puede usar un módulo. Si se le permite usar un módulo, el período de pisano es la mejor manera de hacerlo.
mentatkgs
4

¿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

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

alex
fuente
1
La razón para tener que asignar un generador a una variable es porque [fibs().next() for ...]cada vez se crearía un nuevo generador.
tox123
3

Como sugirió @alex , podría usar una función de generador para hacer esto secuencialmente en lugar de recursivamente.

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
Martineau
fuente
2

Muchos recomiendan que aumentar el límite de recursión sea una buena solución, sin embargo, no lo es porque siempre habrá un límite. En su lugar, use 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)
Harun ERGUL
fuente
1

Quería darle un ejemplo para usar la memorización para calcular Fibonacci, ya que esto le permitirá calcular números significativamente mayores utilizando la recursividad:

cache = {}
def fib_dp(n):
    if n in cache:
        return cache[n]
    if n == 0: return 0
    elif n == 1: return 1
    else:
        value = fib_dp(n-1) + fib_dp(n-2)
    cache[n] = value
    return value

print(fib_dp(998))

Esto todavía es recursivo, pero utiliza una tabla hash simple que permite la reutilización de números de Fibonacci calculados previamente en lugar de volver a hacerlos.

usuario3393266
fuente
1
import sys
sys.setrecursionlimit(1500)

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

c = 998
print(fib(c, 0))
usuario11462758
fuente
1
Esta misma respuesta se ha dado muchas veces. Por favor quítelo.
ZF007
0

Podemos hacerlo usando @lru_cachedecorador y setrecursionlimit()método:

import sys
from functools import lru_cache

sys.setrecursionlimit(15000)


@lru_cache(128)
def fib(n: int) -> int:
    if n == 0:
        return 0
    if n == 1:
        return 1

    return fib(n - 2) + fib(n - 1)


print(fib(14000))

Salida

3002468761178461090995494179715025648692747937490792943468375429502230242942284835863402333575216217865811638730389352239181342307756720414619391217798542575996541081060501905302157019002614964717310808809478675602711440361241500732699145834377856326394037071666274321657305320804055307021019793251762830816701587386994888032362232198219843549865275880699612359275125243457132496772854886508703396643365042454333009802006384286859581649296390803003232654898464561589234445139863242606285711591746222880807391057211912655818499798720987302540712067959840802106849776547522247429904618357394771725653253559346195282601285019169360207355179223814857106405285007997547692546378757062999581657867188420995770650565521377874333085963123444258953052751461206977615079511435862879678439081175536265576977106865074099512897235100538241196445815568291377846656352979228098911566675956525644182645608178603837172227838896725425605719942300037650526231486881066037397866942013838296769284745527778439272995067231492069369130289154753132313883294398593507873555667211005422003204156154859031529462152953119957597195735953686798871131148255050140450845034240095305094449911578598539658855704158240221809528010179414493499583473568873253067921639513996596738275817909624857593693291980841303291145613566466575233283651420134915764961372875933822262953420444548349180436583183291944875599477240814774580187144637965487250578134990402443365677985388481961492444981994523034245619781853365476552719460960795929666883665704293897310201276011658074359194189359660792496027472226428571547971602259808697441435358578480589837766911684200275636889192254762678512597000452676191374475932796663842865744658264924913771676415404179920096074751516422872997665425047457428327276230059296132722787915300105002019006293320082955378715908263653377755031155794063450515731009402407584683132870206376994025920790298591144213659942668622062191441346200098342943955169522532574271644954360217472458521489671859465232568419404182043966092211744372699797375966048010775453444600153524772238401414789562651410289808994960533132759532092895779406940925252906166612153699850759933762897947175972147868784008320247586210378556711332739463277940255289047962323306946068381887446046387745247925675240182981190836264964640612069909458682443392729946084099312047752966806439331403663934969942958022237945205992581178803606156982034385347182766573351768749665172549908638337611953199808161937885366709285043276595726484068138091188914698151703122773726725261370542355162118164302728812259192476428938730724109825922331973256105091200551566581350508061922762910078528219869913214146575557249199263634241165352226570749618907050553115468306669184485910269806225894530809823102279231750061652042560772530576713148647858705369649642907780603247428680176236527220826640665659902650188140474762163503557640566711903907798932853656216227739411210513756695569391593763704981001125

Fuente

functools lru_cache

Emma
fuente
0

También podríamos usar una variación del enfoque ascendente de programación dinámica

def fib_bottom_up(n):

    bottom_up = [None] * (n+1)
    bottom_up[0] = 1
    bottom_up[1] = 1

    for i in range(2, n+1):
        bottom_up[i] = bottom_up[i-1] + bottom_up[i-2]

    return bottom_up[n]

print(fib_bottom_up(20000))
algowhiz
fuente