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

semble que vous avez juste besoin de définir une plus grande profondeur de récursion

sys.setrecursionlimit(1500)

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

à partir de python site :

sys.getrecursionlimit()

renvoie la valeur actuelle de la limite de récursion, la valeur maximale profondeur de la pile d'interpréteurs Python. Cette limite empêche la récursion infinie de causer un débordement de la pile C et un crash de Python. Il peut être défini par setrecursionlimit().

utilise un langage qui garantit l'optimisation de l'appel de queue. Ou utilisez itération. Alternativement, obtenez mignon avec décorateurs .

je me rends compte que c'est une vieille question mais pour ceux qui lisent, je recommande de ne pas utiliser la récursion pour des problèmes comme celui - ci-les listes sont beaucoup plus rapides et éviter la récursion entièrement. Je l'implémenterais 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 de fibonacci à partir de 0 au lieu de 1.)

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 le font remarquer les commentateurs, ce n'est pas O(1) mais O(n) à cause de 2**n . Une différence est que vous obtenez seulement une valeur, alors qu'avec la récursivité vous obtenir toutes les valeurs de Fibonacci(n) jusqu'à cette valeur.

j'ai eu un problème similaire avec l'erreur"recursion max depth exceededed". J'ai découvert que l'erreur était déclenchée par un fichier corrompu dans le répertoire où j'étais avec os.marche. Si vous avez de la difficulté à résoudre ce problème et que vous travaillez avec file paths, assurez-vous de le réduire, car il pourrait s'agir d'un fichier corrompu.

resource.setrlimit doit aussi être utilisé pour augmenter la taille de la cheminée et prévenir segfault

le noyau Linux limite la pile de processus.

Python stocke les variables locales sur la pile de l'interpréteur, et donc la récursion prend l'espace de la pile de l'interpréteur.

si L'interpréteur Python essaie de dépasser la limite de pile, le noyau Linux le segmente par défaut.

la pile la taille limite est contrôlée par les appels système getrlimit et setrlimit .

Python offre l'accès à ces appels système via le module 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)

bien sûr, si vous continuez à augmenter ulimit, votre RAM s'épuisera, ce qui ralentira votre ordinateur à un arrêt dû à la folie de l'échange, ou tuera Python via le tueur de la salle de bain.

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

ulimit -s
ulimit -s 10000

valeur par défaut pour moi est 8Mb.

voir aussi:

• Réglage de stacksize dans un script python
• Python: Quelle est la limite de récursion pour Linux, Mac et Windows?

testé sur Ubuntu 16.10, Python 2.7.12.

utiliser 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

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

beaucoup recommandent que l'augmentation de la limite de récursion est une bonne solution mais ce n'est pas parce qu'il y aura toujours 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)

si vous voulez obtenir seulement quelques nombres de Fibonacci, vous pouvez utiliser la méthode de matrice.

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 parce qu'elle n'utilise que des entiers. Mais si vous voulez tous les numéros Fibonacci jusqu'à n, Alors il est préférable de le faire par mémorisation.

si vous avez souvent besoin de changer la limite de récursion (par exemple en résolvant des puzzles de programmation) vous pouvez définir un simple gestionnaire de contexte comme ceci:

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

lors de la sortie du corps de la déclaration with la limite de récursion sera restaurée à la valeur par défaut.

comme @alex suggéré , vous pouvez utiliser une fonction de générateur pour faire cela. 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