Qual é a profundidade máxima de recursão no Python e como aumentá-la?

421

Eu tenho essa função recursiva da cauda aqui:

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 até n=997, então apenas quebra e cospe a RecursionError: maximum recursion depth exceeded in comparison. Isso é apenas um estouro de pilha? Existe uma maneira de contornar isso?

quantumSoup
fonte
3
Veja também stackoverflow.com/questions/5061582/…
Thomas Ahle 28/04
9
A memorização pode acelerar sua função e aumentar sua profundidade recursiva efetiva, fazendo com que os valores calculados anteriormente terminem em vez de aumentar o tamanho da pilha.
Cyoce 11/01
2
O limite de recursão é normalmente 1000.
Boris
1
@tonix, o intérprete adiciona um quadro de pilha (os line <n>, in <module>rastreamentos na pilha) e esse código leva 2 quadros de pilha para n=1(porque o caso base é n < 1, portanto n=1ainda é recorrente). E acho que o limite de recursão não é inclusivo, como no erro "erro ao atingir 1000" não "se você exceder 1000 (1001)". 997 + 2é menor que 1000, portanto, 998 + 2não funciona porque atinge o limite.
Boris
1
@tonix no. recursive_function(997)funciona, quebra em 998. Quando você chama, recursive_function(998)ele usa 999 quadros de pilha e 1 quadro é adicionado pelo intérprete (porque seu código é sempre executado como se fosse parte do módulo de nível superior), o que faz com que atinja o limite de 1000.
Boris

Respostas:

469

É uma proteção contra um estouro de pilha, sim. Python (ou melhor, a implementação do CPython) não otimiza a recursão de cauda, ​​e a recursão desenfreada causa estouros de pilha. Você pode verificar o limite de recursão sys.getrecursionlimite alterar o limite de recursão com sys.setrecursionlimit, mas isso é perigoso - o limite padrão é um pouco conservador, mas os quadros de pilha Python podem ser bastante grandes.

Python não é uma linguagem funcional e a recursão da cauda não é uma técnica particularmente eficiente. Reescrever o algoritmo iterativamente, se possível, geralmente é uma idéia melhor.

Thomas Wouters
fonte
4
Da minha experiência, você precisa aumentar o limite, tanto nos syse os resourcemódulos: stackoverflow.com/a/16248113/205521
Thomas Ahle
3
como uma tática para convertê-lo para uma versão iterativa, um decorador de cauda chamada optimização poderia ser usado
jfs
3
você pode usar svn.python.org/projects/python/trunk/Tools/scripts/… para descobrir o limite superior do sistema operacional
Ullullu
8
Para os interessados ​​na fonte, o limite de recursão padrão é definido como 1000 hg.python.org/cpython/file/tip/Python/ceval.c#l691 e pode ser alterado usando a API em hg.python.org/cpython /file/tip/Python/sysmodule.c#l643, que por sua vez define o limite para o novo valor em hg.python.org/cpython/file/tip/Python/ceval.c#l703
Pramod,
17
A recursão da cauda é uma técnica perfeitamente eficiente em uma linguagem de programação otimizada para ela. Para o tipo certo de problema, pode ser consideravelmente mais expressivo e uma implementação iterativa. A resposta provavelmente significa "em Python especificamente", mas que não é o que diz
Peter R
136

Parece que você só precisa definir uma profundidade de recursão mais alta :

import sys
sys.setrecursionlimit(1500)
David Young
fonte
No meu caso, esqueci a declaração de retorno no caso base e passou a exceder 1000. Python começou a lançar essa exceção e fiquei surpreso, porque tinha certeza de que não. de pilhas que vai criar para executá-lo.
vijayraj34 19/05/19
sys.setrecursionlimit (50) ou uma pequena quantidade é útil se o seu programa estiver inserindo recursão e você desejar que a mensagem de erro NÃO seja páginas e páginas do mesmo texto. Achei isso muito útil ao depurar (meu) código recursivo incorreto.
peawormsworth 22/02
56

É para evitar um estouro de pilha. O intérprete Python limita a profundidade da recursão para ajudar a evitar recursões infinitas, resultando em estouros de pilha. Tente aumentar o limite de recursão ( sys.setrecursionlimit) ou reescreva seu código sem recursão.

Na documentação do Python :

sys.getrecursionlimit()

Retorne o valor atual do limite de recursão, a profundidade máxima da pilha do interpretador Python. Esse limite evita que a recursão infinita cause um estouro da pilha C e trava o Python. Pode ser definido por setrecursionlimit().

Scharron
fonte
No meu Anaconda x64, 3,5 Python no Windows, o limite padrão é 1000.
Guillaume Chevalier
30

Se você precisar alterar frequentemente o limite de recursão (por exemplo, ao resolver quebra-cabeças de programação), poderá definir um gerenciador de contexto simples 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)

Em seguida, para chamar uma função com um limite personalizado, você pode:

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

Ao sair do corpo da withinstrução, o limite de recursão será restaurado para o valor padrão.

Eugene Yarmash
fonte
Você também deseja aumentar o limite de recursão do processo comresource . Sem ele, você receberá uma falha de segmentação e todo o processo Python falhará se você for setrecursionlimitalto demais e tentar usar o novo limite (cerca de 8 megabytes de quadros de pilha, que se traduz em ~ 30.000 quadros de pilha com a função simples acima, em meu notebook).
Boris
16

Use uma linguagem que garanta otimização de chamada de cauda. Ou use a iteração. Como alternativa, fique fofo com os decoradores .

Marcelo Cantos
fonte
36
Isso é jogar o bebê fora com a água do banho.
Russell Borogove
3
@ Russell: Apenas uma das opções que ofereci aconselha isso.
Marcelo Cantos
"Ficar fofo com decoradores" não é exatamente uma opção.
Sr. B
@ Mr.B a menos que você precisa mais do que ulimit -sde quadros de pilha, sim, é stackoverflow.com/a/50120316
Boris
14

resource.setrlimit também deve ser usado para aumentar o tamanho da pilha e evitar segfault

O kernel do Linux limita a pilha de processos .

O Python armazena variáveis ​​locais na pilha do intérprete e, portanto, a recursão ocupa o espaço da pilha do intérprete.

Se o intérprete Python tentar ultrapassar o limite da pilha, o kernel do Linux fará uma falha na segmentação.

O tamanho do limite da pilha é controlado com as chamadas getrlimite do setrlimitsistema.

O Python oferece acesso a essas chamadas do sistema através do 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)

Obviamente, se você continuar aumentando o ulimit, sua RAM acabará, o que reduzirá a velocidade do computador devido a uma loucura de troca ou matará o Python pelo OOM Killer.

No bash, você pode ver e definir o limite da pilha (em kb) com:

ulimit -s
ulimit -s 10000

O valor padrão para mim é 8Mb.

Veja também:

Testado no Ubuntu 16.10, Python 2.7.12.

Ciro Santilli adicionou uma nova foto
fonte
1
Tentar definir rlimit_stackapós as correções do Stack Clash pode resultar em falha ou problemas relacionados. Veja também a Edição 1463241 da
jww
Eu usei isso (a parte do recurso Python) para ajudar minha implementação do algoritmo de Kosaraju no conjunto de dados médio (grande) do professor Tim Roughgarden. Minha implementação funcionou em pequenos conjuntos, certamente o problema com um grande conjunto de dados foi o limite de recursão / pilha ... Ou foi? Bem, sim foi! Obrigado!
Nilo
9

Sei que essa é uma pergunta antiga, mas para aqueles que lêem, eu recomendaria não usar a recursão para problemas como este - as listas são muito mais rápidas e evitam a recursão por completo. Eu implementaria isso 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 em xrange se começar a contar sua sequência de fibonacci de 0 em vez de 1.)

Daniel
fonte
13
por que usar O (n) espaço quando você pode usar O (1)?
Janus Troelsen
11
Apenas no caso de o comentário de O (n) space ser confuso: não use uma lista. A lista manterá todos os valores quando tudo que você precisa é o enésimo valor. Um algoritmo simples seria manter os dois últimos números de fibonacci e adicioná-los até chegar ao que você precisa. Existem algoritmos melhores também.
Milimétrico 14/07
3
@Mathime: xrangeé chamado simplesmente range, em Python 3.
Eric O Lebigot
1
@EOL Estou ciente disso
Mathime 3/16/16
7
@Mathime Eu estava explicitando as coisas para quem lê esses comentários.
Eric O Lebigot
9

Obviamente, os números de Fibonacci podem ser calculados em O (n) aplicando a fórmula 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 observam os comentaristas, não é O (1), mas O (n) por causa de 2**n. A diferença também é que você obtém apenas um valor, enquanto que com a recursão você obtém todos os valores Fibonacci(n)até esse valor.

rwst
fonte
8
Não há tamanho máximo de um longo em python.
pppery
8
Vale a pena notar que isso falha muito por ncausa da imprecisão do ponto flutuante - a diferença entre (1+sqrt(5))**ne (1+sqrt(5))**(n+1)se torna menor que 1 ulp, para que você comece a obter resultados incorretos.
2
Há realmente não é grande inteiros no NumPy ...
Eric O Lebigot
@Mego What? É a diferença entre (1+sqrt(5))**ne ((1+sqrt(5))**n)+1isso se torna menor que 1 ulp! (erro de digitação pequeno) Além disso, {@} rwst Isso não é O (1)! O cálculo 2**nleva pelo menos O (n) tempo.
usar o seguinte comando
3
@ user202729 Isso não é verdade, o cálculo 2**né efetivamente O (log (n)) usando a exponenciação ao quadrado .
Sam
6

Eu tive um problema semelhante com o erro "Profundidade máxima de recursão excedida". Descobri que o erro estava sendo acionado por um arquivo corrompido no diretório em que eu estava repetindo os.walk. Se você tiver problemas para resolver esse problema e estiver trabalhando com caminhos de arquivo, reduza-o, pois pode ser um arquivo corrompido.

Tyler
fonte
2
O OP fornece seu código e seu experimento é reproduzível à vontade. Não envolve arquivos corrompidos.
505 Verron
5
Você está certo, mas minha resposta não está voltada para o OP, pois isso foi há mais de quatro anos. Minha resposta tem como objetivo ajudar aqueles com erros de MRD causados ​​indiretamente por arquivos corrompidos - já que este é um dos primeiros resultados da pesquisa. Ajudou alguém, já que foi votado. Obrigado pelo voto negativo.
Tyler
2
Essa foi a única coisa que encontrei em qualquer lugar ao pesquisar o meu problema que conectou um rastreamento de "profundidade máxima de recursão máxima" a um arquivo corrompido. Obrigado!
18717 Jeff Jeff
5

Se você deseja obter apenas alguns números de Fibonacci, pode usar o método de matriz.

from numpy import matrix

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

É rápido como numpy usa o algoritmo de exponenciação rápida. Você obtém resposta em O (log n). E é melhor que a fórmula de Binet, porque usa apenas números inteiros. Mas se você deseja que todos os números de Fibonacci sejam n, é melhor fazê-lo por memorização.

bebidek
fonte
Infelizmente, você não pode usar numpy na maioria dos juízes de programação competitivos. Mas sim senhor, sua solução é a minha favorita. Eu usei a solução de matriz para alguns problemas. É a melhor solução quando você precisa de um número muito grande de fibonacci e não pode usar um módulo. Se você tiver permissão para usar um módulo, o período pisano é a melhor maneira de fazê-lo.
mentatkgs
4

Use geradores?

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

função fib () acima adaptada de: http://intermediatepythonista.com/python-generators

alex
fonte
1
a razão para ter que atribuir um gerador a uma variável é porque [fibs().next() for ...]criaria um novo gerador a cada vez.
tox123
3

Como o @alex sugeriu , você pode usar uma função geradora para fazer isso sequencialmente, em vez de recursivamente.

Aqui está o equivalente do código na sua pergunta:

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
fonte
2

Muitos recomendam que aumentar o limite de recursão seja uma boa solução, mas não é porque sempre haverá limite. Em vez disso, use uma solução 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
fonte
1

Eu queria dar um exemplo para usar a memorização para calcular Fibonacci, pois isso permitirá que você calcule números significativamente maiores usando recursão:

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))

Isso ainda é recursivo, mas usa uma hashtable simples que permite a reutilização de números de Fibonacci calculados anteriormente, em vez de fazê-los novamente.

user3393266
fonte
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))
user11462758
fonte
1
Essa mesma resposta foi dada muitas vezes. Por favor, remova-o.
ZF007 19/06/19
0

Podemos fazer isso usando o @lru_cachedecorador e o 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))

Resultado

3002468761178461090995494179715025648692747937490792943468375429502230242942284835863402333575216217865811638730389352239181342307756720414619391217798542575996541081060501905302157019002614964717310808809478675602711440361241500732699145834377856326394037071666274321657305320804055307021019793251762830816701587386994888032362232198219843549865275880699612359275125243457132496772854886508703396643365042454333009802006384286859581649296390803003232654898464561589234445139863242606285711591746222880807391057211912655818499798720987302540712067959840802106849776547522247429904618357394771725653253559346195282601285019169360207355179223814857106405285007997547692546378757062999581657867188420995770650565521377874333085963123444258953052751461206977615079511435862879678439081175536265576977106865074099512897235100538241196445815568291377846656352979228098911566675956525644182645608178603837172227838896725425605719942300037650526231486881066037397866942013838296769284745527778439272995067231492069369130289154753132313883294398593507873555667211005422003204156154859031529462152953119957597195735953686798871131148255050140450845034240095305094449911578598539658855704158240221809528010179414493499583473568873253067921639513996596738275817909624857593693291980841303291145613566466575233283651420134915764961372875933822262953420444548349180436583183291944875599477240814774580187144637965487250578134990402443365677985388481961492444981994523034245619781853365476552719460960795929666883665704293897310201276011658074359194189359660792496027472226428571547971602259808697441435358578480589837766911684200275636889192254762678512597000452676191374475932796663842865744658264924913771676415404179920096074751516422872997665425047457428327276230059296132722787915300105002019006293320082955378715908263653377755031155794063450515731009402407584683132870206376994025920790298591144213659942668622062191441346200098342943955169522532574271644954360217472458521489671859465232568419404182043966092211744372699797375966048010775453444600153524772238401414789562651410289808994960533132759532092895779406940925252906166612153699850759933762897947175972147868784008320247586210378556711332739463277940255289047962323306946068381887446046387745247925675240182981190836264964640612069909458682443392729946084099312047752966806439331403663934969942958022237945205992581178803606156982034385347182766573351768749665172549908638337611953199808161937885366709285043276595726484068138091188914698151703122773726725261370542355162118164302728812259192476428938730724109825922331973256105091200551566581350508061922762910078528219869913214146575557249199263634241165352226570749618907050553115468306669184485910269806225894530809823102279231750061652042560772530576713148647858705369649642907780603247428680176236527220826640665659902650188140474762163503557640566711903907798932853656216227739411210513756695569391593763704981001125

Fonte

functools lru_cache

Emma
fonte
0

Também poderíamos usar uma variação da abordagem dinâmica de baixo para cima para programação

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
fonte