Python optimise-t-il la récursion de queue ?

Question

J'ai le morceau de code suivant qui échoue avec l'erreur suivante :

RuntimeError : profondeur maximale de récursion dépassée

J'ai tenté de le réécrire pour permettre l'optimisation de la récursion de la queue (TCO). Je pense que ce code aurait dû réussir si une TCO avait eu lieu.

def trisum(n, csum):
    if n == 0:
        return csum
    else:
        return trisum(n - 1, csum + n)

print(trisum(1000, 0))

Dois-je en conclure que Python ne fait aucun type de TCO, ou dois-je simplement le définir différemment ?

Answer 1

Non, et ça n'arrivera jamais puisque Guido préfère avoir des traces de son passage.

http://neopythonic.blogspot.com.au/2009/04/tail-recursion-elimination.html

http://neopythonic.blogspot.com.au/2009/04/final-words-on-tail-calls.html

Vous pouvez éliminer manuellement la récursion avec une transformation comme celle-ci

>>> def trisum(n, csum):
...     while True:                     # change recursion to a while loop
...         if n == 0:
...             return csum
...         n, csum = n - 1, csum + n   # update parameters instead of tail recursion

>>> trisum(1000,0)
500500

Answer 2

J'ai écrit un tout petit plugin pour gérer la récursion de queue. Vous pouvez le trouver avec mes explications ici : https://groups.google.com/forum/?hl=fr#!topic/comp.lang.python/dIsnJ2BoBKs

Il peut intégrer une fonction lambda écrite avec un style de récursion de queue dans une autre fonction qui l'évaluera comme une boucle.

La caractéristique la plus intéressante de cette petite fonction, à mon humble avis, est qu'elle ne repose pas sur une astuce de programmation malhonnête mais sur le simple lambda calculus : le comportement de la fonction est modifié lorsqu'elle est insérée dans une autre fonction lambda qui ressemble beaucoup au Y-combinator.

Regards.

Answer 3

Le mot de Guido est à http://neopythonic.blogspot.co.uk/2009/04/tail-recursion-elimination.html

J'ai récemment publié un article dans mon blogue sur l'histoire de Python sur les origines des fonctionnalités de Python. fonctionnalités de Python. Une remarque sur le fait de ne pas supporter l'élimination des l'élimination de la récursion de queue (TRE) a immédiatement déclenché plusieurs commentaires sur sur le fait qu'il est dommage que Python ne le fasse pas. d'autres personnes essayant de "prouver" que TRE peut être ajoutée facilement à Python. à Python facilement. Laissez-moi donc défendre ma position (qui est que je ne veux pas de TRE dans le langage). que je ne veux pas de TRE dans le langage). Si vous voulez une réponse courte, c'est tout simplement non python. Voici la réponse longue :

Answer 4

CPython ne supporte pas et ne supportera probablement jamais l'optimisation des appels de queue d'après les déclarations de Guido sur le sujet. J'ai entendu des arguments selon lesquels cela rend le débogage plus difficile en raison de la façon dont cela modifie la trace de la pile.