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

Question

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

Il fonctionne jusqu'à n=997 puis il se brise et crache un RecursionError: maximum recursion depth exceeded in comparison . S'agit-il simplement d'un débordement de pile ? Existe-t-il un moyen de le contourner ?

Answer 1

C'est une protection contre un débordement de pile, oui. Python (ou plutôt, l'implémentation CPython) n'optimise pas la récursion de queue, et la récursion débridée provoque des débordements de pile. Vous pouvez vérifier la limite de récursion avec sys.getrecursionlimit :

import sys
print(sys.getrecursionlimit())

et modifier la limite de récursion avec sys.setrecursionlimit :

sys.setrecursionlimit(1500)

mais le faire est dangereux -- la limite standard est un peu conservatrice, mais les cadres de pile Python peuvent être assez grands.

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

Answer 2

On dirait que vous avez juste besoin de définir une profondeur de récursion plus élevée :

import sys
sys.setrecursionlimit(1500)

Answer 3

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

De la Documentation Python :

sys.getrecursionlimit()

Retourne la valeur actuelle de la limite de récursion, la profondeur maximale de la pile de l'interpréteur Python. Cette limite empêche la récursion infinie de provoquer un débordement de la pile C et de faire planter Python. Elle peut être définie par setrecursionlimit() .

Answer 4

Utilisez un langage qui garantit l'optimisation des appels de queue. Ou utilisez l'itération. Ou encore, faites-vous plaisir avec décorateurs .

Answer 5

Je me rends compte qu'il s'agit d'une vieille question mais pour ceux qui lisent, je recommanderais de ne pas utiliser la récursion pour des problèmes comme celui-ci - les listes sont beaucoup plus rapides et évitent entièrement la récursion. J'implémenterais ceci 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).