Pourquoi Python a-t-il une profondeur de récursion maximale?
Python a une profondeur de récursion maximale, mais pas de profondeur d'itération maximale. Pourquoi la récursion est-elle restreinte? Ne serait-il pas plus naturel de traiter la récursivité comme itération, et ne pas limiter le nombre d'appels récursifs?
Permettez-moi juste de dire que la source de cette question est venue d'essayer d'implémenter un stream (voir cette question pour plus de détails sur les flux). Par exemple, disons que nous voulons écrire un flux pour produire les nombres naturels:
def stream_accum(s, n): # force the stream to a list of length n
def loop(s, acc):
if len(acc) == n:
return acc
hd, tl = s()
return loop(tl, acc + [hd])
return loop(s, [])
def nats():
def loop(n):
return n, lambda: loop(n+1)
return loop(1)
Le définition récursive de flux est très attrayant. Cependant, je suppose que l'approche meilleure/plus pythonique serait d'utiliser des générateurs.
3 réponses
il y a en fait quelques problèmes ici.
tout d'Abord, comme réponse de NPE explique bien, Python n'élimine pas les appels de queue, donc beaucoup de fonctions qui permettraient une récursion illimitée dans, disons, Scheme sont limitées en Python.
Deuxièmement, comme expliqué par NPE, les appels qui ne peuvent pas être éliminés prennent de l'espace sur la pile d'appels. Et, même dans les langues qui font du TCE, il y a beaucoup de fonctions récursives qui ne peuvent pas être traitées comme des itérations. (Tenir compte de la fonction Fibonacci naïve qui se rappelle deux fois.)
Mais pourquoi la pile d'appel, une ressource limitée, en premier lieu? Les cadres de pile Python peuvent au moins en principe être implémentés sur le tas et reliés entre eux (voir Stackless pour une preuve d'existence de ce principe), et dans un espace mémoire 64 bits, il y a de la place pour beaucoup plus de 1000 images de pile. (En fait, même la pile C sur presque n'importe quelle plate-forme moderne peut contenir beaucoup plus de 1000 appels d'interpréteur Python récursifs.)
une partie de la raison est historique: l'interpréteur Python stock utilise la pile c fixe pour s'appeler de façon récursive chaque fois que vous faites un appel récursif, et il a été conçu à l'origine pour les plateformes 32 bits (et même 24 ou 20 bits) où cette pile c est assez petite.
Mais cela aurait pu être changé, et Python 3.0 aurait été un endroit parfait pour se changer. Alors, pourquoi n'ont-ils pas? Parce qu'ils ont fait une conception consciente du langage décision. En code pythonique, la récursion est généralement très superficielle (par exemple, un code comme os.walk qui traverse des structures d'arbres peu profondes); si votre fonction atteint une profondeur de près de 1000, il est plus probable qu'il s'agisse d'un bug que d'un bug intentionnel. Ainsi, la limite reste. Bien sûr, c'est un peu circulaire-s'ils supprimaient la limite (et surtout, s'ils éliminaient les appels de queue), une plus grande récursion deviendrait plus idiomatique. Mais C'est un peu le point-Guido ne veut pas d'un langage où la profonde récursion est idiomatique. (Et la plupart de la communauté Python est d'accord.)
ce N'est pas unique à Python, et a à voir avec chaque appel prenant de l'espace sur le pile d'appels, et la taille de la pile étant limitée.
L'itération seule ne consomme pas d'espace dans la pile et n'est donc pas soumise à cette limite.
tous les appels récursifs n'ont pas besoin de consommer l'espace de pile. Par exemple, certaines langues peuvent automatiquement transformer recursion de la queue dans l'itération. Cependant, Disponible choisit de ne pas le faire ( Python optimise-t-il la récursion de la queue?).
Vous pouvez augmenter la profondeur maximale de l'Python pile d'appel en appelant sys.setrecursionlimit.
la récursion nécessite de l'espace sur le pile d'appels, qui est de taille limitée. Le Code qui utilise trop de niveaux de récursion donnera une erreur appelée stack overflow (rendu célèbre par obscur site web). Python semble limiter cette (un peu arbitrairement) à 1000 niveaux, mais ce peut être augmentée en paramètre sys.setrecursionlimit.
Itération utilise quelque chose comme for - boucle, qui est mis en œuvre en incrémentant certains compteur et réglage conditionnel du pointeur d'instruction retour au début de la boucle. Elle est constante dans la mémoire.