Quelle est la profondeur de récursivité maximale en Python et comment l'augmenter?

423

J'ai cette fonction récursive de queue ici:

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

Ça marche n=997, puis ça casse et crache a RecursionError: maximum recursion depth exceeded in comparison. Est-ce juste un débordement de pile? Y a-t-il un moyen de le contourner?

quantumSoup
la source
3
Voir aussi stackoverflow.com/questions/5061582/…
Thomas Ahle
9
la mémorisation pourrait accélérer votre fonction et augmenter sa profondeur récursive effective en faisant terminer les valeurs précédemment calculées au lieu d'augmenter la taille de la pile.
Cyoce
2
La limite de récursivité est généralement de 1000.
Boris
1
@tonix l'interpréteur ajoute un cadre de pile (les line <n>, in <module>traces dans la pile) et ce code prend 2 cadres de pile pour n=1(parce que le cas de base l'est n < 1, donc n=1il revient toujours). Et je suppose que la limite de récursivité n'est pas inclusive, comme dans son "erreur lorsque vous frappez 1000" et non "erreur si vous dépassez 1000 (1001)". 997 + 2est inférieur à 1000, donc cela 998 + 2ne fonctionne pas car il atteint la limite.
Boris
1
@tonix no. recursive_function(997)ça marche, ça casse 998. Lorsque vous l'appelez, recursive_function(998)il utilise 999 cadres de pile et 1 cadre est ajouté par l'interpréteur (car votre code est toujours exécuté comme s'il faisait partie du module de niveau supérieur), ce qui le fait atteindre la limite de 1000.
Boris

Réponses:

470

C'est une protection contre un débordement de pile, oui. Python (ou plutôt, l'implémentation CPython) n'optimise pas la récursivité de queue, et la récursion débridée provoque des débordements de pile. Vous pouvez vérifier la limite de récursivité avec sys.getrecursionlimitet modifier la limite de récursivité avec sys.setrecursionlimit, mais cela est dangereux - la limite standard est un peu conservatrice, mais les stackframes Python peuvent être assez gros.

Python n'est pas un langage fonctionnel et la récursivité de la queue n'est pas une technique particulièrement efficace. La réécriture itérative de l'algorithme, si possible, est généralement une meilleure idée.

Thomas Wouters
la source
4
D'après mon expérience, vous devez augmenter la limite dans sysles resourcemodules et: stackoverflow.com/a/16248113/205521
Thomas Ahle
3
comme tactique pour le convertir en une version itérative, un décorateur d'optimisation des appels de queue pourrait être utilisé
jfs
3
vous pouvez utiliser svn.python.org/projects/python/trunk/Tools/scripts/… pour connaître la limite supérieure de votre système d'exploitation
Ullullu
8
Pour ceux qui s'intéressent à la source, la limite de récursivité par défaut est définie sur 1000 hg.python.org/cpython/file/tip/Python/ceval.c#l691 et elle peut être modifiée à l'aide de l'API à hg.python.org/cpython /file/tip/Python/sysmodule.c#l643 qui à son tour fixe la limite à la nouvelle valeur à hg.python.org/cpython/file/tip/Python/ceval.c#l703
Pramod
17
La récursivité de la queue est une technique parfaitement efficace dans un langage de programmation optimisé pour cela. Pour le bon type de problème, il peut être considérablement plus expressif et implémenté de manière itérative. La réponse signifie probablement "en Python spécifiquement" mais ce n'est pas ce qu'elle dit
Peter R
137

Il semble que vous ayez juste besoin de définir une profondeur de récursivité plus élevée :

import sys
sys.setrecursionlimit(1500)
David Young
la source
Dans mon cas, j'ai oublié la déclaration de retour dans le cas de base et elle a dépassé 1000. Python a commencé à lever cette exception et j'ai été étonné, car j'étais sûr du non. de piles sa va créer pour l'exécuter.
vijayraj34
sys.setrecursionlimit (50) ou une petite quantité est utile si votre programme entre en récursivité et que vous souhaitez que le message d'erreur ne soit PAS des pages et des pages du même texte. J'ai trouvé cela très utile lors du débogage de (mon) mauvais code récursif.
peawormsworth
56

C'est pour éviter un débordement de pile. L'interpréteur Python limite les profondeurs de récursivité pour vous aider à éviter les récursions infinies, entraînant des débordements de pile. Essayez d'augmenter la limite de récursivité ( sys.setrecursionlimit) ou de réécrire votre code sans récursivité.

Dans la documentation Python :

sys.getrecursionlimit()

Renvoie la valeur actuelle de la limite de récursivité, la profondeur maximale de la pile d'interpréteur Python. Cette limite empêche une récursion infinie de provoquer un débordement de la pile C et de planter Python. Il peut être réglé par setrecursionlimit().

Scharron
la source
Sur mon Anaconda x64, 3.5 Python sous Windows, la limite par défaut est de 1000.
Guillaume Chevalier
30

Si vous devez souvent modifier la limite de récursivité (par exemple lors de la résolution d'énigmes de programmation), vous pouvez définir un gestionnaire de contexte simple comme celui-ci:

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)

Ensuite, pour appeler une fonction avec une limite personnalisée, vous pouvez faire:

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

À la sortie du corps de l' withinstruction, la limite de récursivité sera restaurée à la valeur par défaut.

Eugene Yarmash
la source
Vous souhaitez également augmenter la limite de récursivité du processus avecresource . Sans cela, vous obtiendrez une erreur de segmentation et l'ensemble du processus Python se bloquera si vous êtes setrecursionlimittrop élevé et essayez d'utiliser la nouvelle limite (environ 8 mégaoctets de cadres de pile, ce qui se traduit par ~ 30 000 cadres de pile avec la fonction simple ci-dessus, sur mon ordinateur portable).
Boris
16

Utilisez un langage qui garantit l'optimisation des appels de queue. Ou utilisez l'itération. Alternativement, soyez mignon avec des décorateurs .

Marcelo Cantos
la source
36
C'est plutôt jeter le bébé avec l'eau du bain.
Russell Borogove
3
@Russell: Une seule des options que j'ai proposées le conseille.
Marcelo Cantos
"Soyez mignon avec les décorateurs" n'est pas exactement une option.
M. B
@ Mr.B sauf si vous avez besoin de plus de ulimit -scadres de pile, oui c'est stackoverflow.com/a/50120316
Boris
14

resource.setrlimit doit également être utilisé pour augmenter la taille de la pile et éviter les erreurs de segmentation

Le noyau Linux limite la pile de processus .

Python stocke des variables locales sur la pile de l'interpréteur, et donc la récursivité occupe l'espace de pile de l'interpréteur.

Si l'interpréteur Python essaie de dépasser la limite de pile, le noyau Linux lui fait un défaut de segmentation.

La taille limite de pile est contrôlée avec les appels système getrlimitet setrlimit.

Python offre un accès à ces appels système via le resourcemodule.

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)

Bien sûr, si vous continuez à augmenter ulimit, votre RAM s'épuisera, ce qui ralentira votre ordinateur à l'arrêt en raison de la folie des échanges, ou tuera Python via OOM Killer.

Depuis bash, vous pouvez voir et définir la limite de pile (en Ko) avec:

ulimit -s
ulimit -s 10000

La valeur par défaut pour moi est de 8 Mo.

Voir également:

Testé sur Ubuntu 16.10, Python 2.7.12.

Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
la source
1
Toute tentative de définition rlimit_stackaprès les corrections de Stack Clash peut entraîner une défaillance ou des problèmes associés. Voir également le numéro 1463241 de
2017 à 16:35
J'ai utilisé cela (la partie ressource Python) pour aider à la mise en œuvre de l'algorithme de Kosaraju sur l'ensemble de données moyen (énorme) du professeur Tim Roughgarden. Mon implémentation a fonctionné sur de petits ensembles, certainement le problème avec un grand ensemble de données était la limite de récursivité / pile ... Ou était-ce? Eh bien, oui! Merci!
nilo
9

Je me rends compte que c'est une vieille question mais pour ceux qui lisent, je recommanderais de ne pas utiliser la récursivité pour des problèmes comme celui-ci - les listes sont beaucoup plus rapides et évitent complètement la récursivité. Je mettrais cela en œuvre comme:

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

(Utilisez n + 1 dans xrange si vous commencez à compter votre séquence fibonacci à partir de 0 au lieu de 1.)

Daniel
la source
13
pourquoi utiliser l'espace O (n) alors que vous pouvez utiliser O (1)?
Janus Troelsen
11
Juste au cas où le commentaire de l'espace O (n) était déroutant: n'utilisez pas de liste. La liste conservera toutes les valeurs lorsque tout ce dont vous avez besoin est la nième valeur. Un algorithme simple serait de conserver les deux derniers nombres de fibonacci et de les ajouter jusqu'à ce que vous obteniez celui dont vous avez besoin. Il existe également de meilleurs algorithmes.
Milimetric
3
@Mathime: xranges'appelle simplement range, en Python 3.
Eric O Lebigot
1
@EOL J'en suis conscient
Mathime
7
@Mathime Je rendais les choses explicites pour ceux qui lisent ces commentaires.
Eric O Lebigot
9

Bien sûr, les nombres de Fibonacci peuvent être calculés en O (n) en appliquant la formule 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))

Comme les commentateurs le notent, ce n'est pas O (1) mais O (n) à cause de 2**n. Une différence est également que vous n'obtenez qu'une seule valeur, tandis qu'avec la récursivité, vous obtenez toutes les valeurs Fibonacci(n)jusqu'à cette valeur.

rwst
la source
8
Il n'y a pas de taille maximale d'un long en python.
pppery
8
Il convient de noter que cela échoue pour une plus grande nraison de l'imprécision en virgule flottante - la différence entre (1+sqrt(5))**net (1+sqrt(5))**(n+1)devient inférieure à 1 ulp, donc vous commencez à obtenir des résultats incorrects.
2
Il n'y a en fait pas de gros nombres entiers dans NumPy…
Eric O Lebigot
@Mego Quoi? C'est la différence entre (1+sqrt(5))**net ((1+sqrt(5))**n)+1qui devient moins de 1 ulp! (petite faute de frappe) Aussi, {@} rwst Ce n'est pas O (1)! Le calcul 2**nprend au moins O (n) temps.
user202729
3
@ user202729 Ce n'est pas vrai, le calcul 2**nest en fait O (log (n)) en utilisant l' exponentiattion par quadrature .
Sam
6

J'ai eu un problème similaire avec l'erreur "Profondeur de récursivité maximale dépassée". J'ai découvert que l'erreur était déclenchée par un fichier corrompu dans le répertoire avec lequel je faisais une boucle os.walk. Si vous rencontrez des problèmes pour résoudre ce problème et que vous travaillez avec des chemins de fichier, assurez-vous de le réduire, car il peut s'agir d'un fichier corrompu.

Tyler
la source
2
L'OP donne son code, et son expérience est reproductible à volonté. Il n'implique pas de fichiers corrompus.
T. Verron
5
Vous avez raison, mais ma réponse n'est pas orientée vers le PO, puisque c'était il y a plus de quatre ans. Ma réponse vise à aider ceux qui ont des erreurs MRD indirectement causées par des fichiers corrompus - car c'est l'un des premiers résultats de recherche. Cela a aidé quelqu'un, car il a été voté. Merci pour le vote négatif.
Tyler
2
C'est la seule chose que j'ai trouvée n'importe où lors de la recherche de mon problème qui a connecté une traceback "profondeur de récurrence maximale" à un fichier corrompu. Merci!
Jeff
5

Si vous ne souhaitez obtenir que quelques nombres de Fibonacci, vous pouvez utiliser la méthode matricielle.

from numpy import matrix

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

C'est rapide car numpy utilise un algorithme d'exponentiation rapide. Vous obtenez la réponse en O (log n). Et c'est mieux que la formule de Binet car elle n'utilise que des entiers. Mais si vous voulez tous les nombres de Fibonacci jusqu'à n, alors il vaut mieux le faire par mémorisation.

bebidek
la source
Malheureusement, vous ne pouvez pas utiliser numpy dans la plupart des juges de programmation compétitifs. Mais oui monsieur, votre solution est ma préférée. J'ai utilisé la dissolution matricielle pour certains problèmes. C'est la meilleure solution lorsque vous avez besoin d'un très grand nombre de fibonacci et que vous ne pouvez pas utiliser de module. Si vous êtes autorisé à utiliser un module, la période pisano est la meilleure façon de le faire.
mentatkgs
4

Utilisez des générateurs?

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

ci-dessus fonction fib () adaptée de: http://intermediatepythonista.com/python-generators

alex
la source
1
la raison pour laquelle il faut attribuer un générateur à une variable est que cela [fibs().next() for ...]créerait un nouveau générateur à chaque fois.
tox123
3

Comme l'a suggéré @alex , vous pouvez utiliser une fonction de générateur pour le faire de manière séquentielle plutôt que récursive.

Voici l'équivalent du code dans votre question:

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
la source
2

Beaucoup recommandent que l'augmentation de la limite de récursivité soit une bonne solution mais ce n'est pas parce qu'il y aura toujours une limite. Utilisez plutôt une solution itérative.

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
la source
1

Je voulais vous donner un exemple d'utilisation de la mémorisation pour calculer Fibonacci car cela vous permettra de calculer des nombres beaucoup plus importants en utilisant la récursivité:

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

C'est encore récursif, mais utilise une table de hachage simple qui permet la réutilisation des nombres de Fibonacci précédemment calculés au lieu de les refaire.

user3393266
la source
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
la source
1
Cette même réponse a été donnée à plusieurs reprises. Veuillez le retirer.
ZF007
0

Nous pouvons le faire en utilisant le @lru_cachedécorateur et la setrecursionlimit()méthode:

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

Production

3002468761178461090995494179715025648692747937490792943468375429502230242942284835863402333575216217865811638730389352239181342307756720414619391217798542575996541081060501905302157019002614964717310808809478675602711440361241500732699145834377856326394037071666274321657305320804055307021019793251762830816701587386994888032362232198219843549865275880699612359275125243457132496772854886508703396643365042454333009802006384286859581649296390803003232654898464561589234445139863242606285711591746222880807391057211912655818499798720987302540712067959840802106849776547522247429904618357394771725653253559346195282601285019169360207355179223814857106405285007997547692546378757062999581657867188420995770650565521377874333085963123444258953052751461206977615079511435862879678439081175536265576977106865074099512897235100538241196445815568291377846656352979228098911566675956525644182645608178603837172227838896725425605719942300037650526231486881066037397866942013838296769284745527778439272995067231492069369130289154753132313883294398593507873555667211005422003204156154859031529462152953119957597195735953686798871131148255050140450845034240095305094449911578598539658855704158240221809528010179414493499583473568873253067921639513996596738275817909624857593693291980841303291145613566466575233283651420134915764961372875933822262953420444548349180436583183291944875599477240814774580187144637965487250578134990402443365677985388481961492444981994523034245619781853365476552719460960795929666883665704293897310201276011658074359194189359660792496027472226428571547971602259808697441435358578480589837766911684200275636889192254762678512597000452676191374475932796663842865744658264924913771676415404179920096074751516422872997665425047457428327276230059296132722787915300105002019006293320082955378715908263653377755031155794063450515731009402407584683132870206376994025920790298591144213659942668622062191441346200098342943955169522532574271644954360217472458521489671859465232568419404182043966092211744372699797375966048010775453444600153524772238401414789562651410289808994960533132759532092895779406940925252906166612153699850759933762897947175972147868784008320247586210378556711332739463277940255289047962323306946068381887446046387745247925675240182981190836264964640612069909458682443392729946084099312047752966806439331403663934969942958022237945205992581178803606156982034385347182766573351768749665172549908638337611953199808161937885366709285043276595726484068138091188914698151703122773726725261370542355162118164302728812259192476428938730724109825922331973256105091200551566581350508061922762910078528219869913214146575557249199263634241165352226570749618907050553115468306669184485910269806225894530809823102279231750061652042560772530576713148647858705369649642907780603247428680176236527220826640665659902650188140474762163503557640566711903907798932853656216227739411210513756695569391593763704981001125

La source

functools lru_cache

Emma
la source
0

Nous pourrions également utiliser une variante de l'approche ascendante de la programmation dynamique

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
la source