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

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

J'ai essayé de réécrire ceci pour permettre l'optimisation de la récursivité de queue (TCO). Je pense que ce code aurait dû réussir si un 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 conclure que Python ne fait aucun type de TCO, ou dois-je simplement le définir différemment?

Non, et ce ne sera jamais le cas puisque Guido van Rossum préfère pouvoir avoir des retraits corrects:

Élimination de la récursivité de la queue (2009-04-22)

Derniers mots sur les appels de queue (2009-04-27)

Vous pouvez éliminer manuellement la récursivité 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

J'ai publié un module effectuant l'optimisation des appels de queue (gérant à la fois le style de récursion de queue et de passage de continuation): https://github.com/baruchel/tco

Optimisation de la récursivité de queue en Python

Il a souvent été affirmé que la récursivité de la queue ne convenait pas à la méthode de codage Pythonic et que l'on ne devrait pas se soucier de la façon de l'intégrer dans une boucle. Je ne veux pas contester ce point de vue; parfois cependant j'aime essayer ou implémenter de nouvelles idées en tant que fonctions récursives de queue plutôt qu'avec des boucles pour diverses raisons (se concentrer sur l'idée plutôt que sur le processus, avoir vingt fonctions courtes sur mon écran en même temps plutôt que seulement trois "Pythonic" fonctions, travailler dans une session interactive plutôt que de modifier mon code, etc.).

L'optimisation de la récursivité de queue en Python est en fait assez simple. Bien qu'il soit dit impossible ou très délicat, je pense qu'il peut être atteint avec des solutions élégantes, courtes et générales; Je pense même que la plupart de ces solutions n'utilisent pas les fonctionnalités Python autrement qu'elles ne le devraient. Des expressions lambda propres fonctionnant avec des boucles très standard conduisent à des outils rapides, efficaces et entièrement utilisables pour implémenter l'optimisation de récursivité de queue.

Pour plus de commodité, j'ai écrit un petit module implémentant une telle optimisation de deux manières différentes. Je voudrais discuter ici de mes deux fonctions principales.

La voie propre: modifier le combinateur Y

Le combinateur Y est bien connu; il permet d'utiliser les fonctions lambda de manière récursive, mais il ne permet pas à lui seul d'incorporer des appels récursifs dans une boucle. Le calcul lambda à lui seul ne peut pas faire une telle chose. Un léger changement dans le combinateur Y peut cependant protéger l'appel récursif à évaluer réellement. L'évaluation peut ainsi être retardée.

Voici la célèbre expression du combinateur Y:

lambda f: (lambda x: x(x))(lambda y: f(lambda *args: y(y)(*args)))

Avec un très léger changement, j'ai pu obtenir:

lambda f: (lambda x: x(x))(lambda y: f(lambda *args: lambda: y(y)(*args)))

Au lieu de s'appeler elle-même, la fonction f renvoie maintenant une fonction effectuant le même appel, mais puisqu'elle le renvoie, l'évaluation peut être effectuée plus tard de l'extérieur.

Mon code est:

def bet(func):
    b = (lambda f: (lambda x: x(x))(lambda y:
          f(lambda *args: lambda: y(y)(*args))))(func)
    def wrapper(*args):
        out = b(*args)
        while callable(out):
            out = out()
        return out
    return wrapper

La fonction peut être utilisée de la manière suivante; voici deux exemples avec les versions récursives de queue de factorielle et de Fibonacci:

>>> from recursion import *
>>> fac = bet( lambda f: lambda n, a: a if not n else f(n-1,a*n) )
>>> fac(5,1)
120
>>> fibo = bet( lambda f: lambda n,p,q: p if not n else f(n-1,q,p+q) )
>>> fibo(10,0,1)
55

De toute évidence, la profondeur de récursivité n'est plus un problème:

>>> bet( lambda f: lambda n: 42 if not n else f(n-1) )(50000)
42

C'est bien sûr le seul véritable objectif de la fonction.

Une seule chose ne peut pas être faite avec cette optimisation: elle ne peut pas être utilisée avec une fonction récursive de queue évaluant une autre fonction (cela vient du fait que les objets retournés appelables sont tous traités comme des appels récursifs supplémentaires sans distinction). Comme je n'ai généralement pas besoin d'une telle fonctionnalité, je suis très satisfait du code ci-dessus. Cependant, afin de fournir un module plus général, j'ai réfléchi un peu plus afin de trouver une solution de contournement pour ce problème (voir la section suivante).

Concernant la rapidité de ce processus (qui n'est pas le vrai problème cependant), il se trouve être assez bon; Les fonctions récursives de queue sont même évaluées beaucoup plus rapidement qu'avec le code suivant à l'aide d'expressions plus simples:

def bet1(func):
    def wrapper(*args):
        out = func(lambda *x: lambda: x)(*args)
        while callable(out):
            out = func(lambda *x: lambda: x)(*out())
        return out
    return wrapper

Je pense que l'évaluation d'une expression, même compliquée, est beaucoup plus rapide que l'évaluation de plusieurs expressions simples, ce qui est le cas dans cette deuxième version. Je n'ai pas gardé cette nouvelle fonction dans mon module, et je ne vois aucune circonstance où elle pourrait être utilisée plutôt que celle "officielle".

Style de passage de continuation avec exceptions

Voici une fonction plus générale; il est capable de gérer toutes les fonctions récursives de queue, y compris celles renvoyant d'autres fonctions. Les appels récursifs sont reconnus à partir d'autres valeurs de retour par l'utilisation d'exceptions. Cette solution est plus lente que la précédente; un code plus rapide pourrait probablement être écrit en utilisant des valeurs spéciales comme "drapeaux" détectés dans la boucle principale, mais je n'aime pas l'idée d'utiliser des valeurs spéciales ou des mots clés internes. Il y a une interprétation amusante de l'utilisation des exceptions: si Python n'aime pas les appels récursifs à la queue, une exception devrait être levée lorsqu'un appel récursif à la queue se produit, et la manière Pythonique sera de capturer l'exception afin de trouver des éléments propres solution, qui est en fait ce qui se passe ici ...

class _RecursiveCall(Exception):
  def __init__(self, *args):
    self.args = args
def _recursiveCallback(*args):
  raise _RecursiveCall(*args)
def bet0(func):
    def wrapper(*args):
        while True:
          try:
            return func(_recursiveCallback)(*args)
          except _RecursiveCall as e:
            args = e.args
    return wrapper

Maintenant, toutes les fonctions peuvent être utilisées. Dans l'exemple suivant, f(n)est évalué à la fonction d'identité pour toute valeur positive de n:

>>> f = bet0( lambda f: lambda n: (lambda x: x) if not n else f(n-1) )
>>> f(5)(42)
42

Bien sûr, on pourrait faire valoir que les exceptions ne sont pas destinées à être utilisées pour rediriger intentionnellement l'interprète (comme une sorte de gotodéclaration ou probablement plutôt une sorte de style de passage de continuation), ce que je dois admettre. Mais, encore une fois, je trouve drôle l'idée d'utiliser tryune seule ligne comme une returndéclaration: nous essayons de renvoyer quelque chose (comportement normal) mais nous ne pouvons pas le faire à cause d'un appel récursif (exception).

Réponse initiale (2013-08-29).

J'ai écrit un très petit plugin pour gérer la récursivité de la queue. Vous pouvez le trouver avec mes explications là-bas: https://groups.google.com/forum/?hl=fr#!topic/comp.lang.python/dIsnJ2BoBKs

Il peut incorporer une fonction lambda écrite avec un style de récursivité 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 que la fonction ne repose pas sur un hack de programmation sale mais sur un simple calcul lambda: le comportement de la fonction est changé en un autre lorsqu'elle est insérée dans une autre fonction lambda qui ressemble beaucoup au combinateur Y.

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

J'ai récemment publié une entrée dans mon blog sur l'histoire de Python sur les origines des fonctionnalités de Python. Une remarque secondaire sur le fait de ne pas prendre en charge l'élimination de la récursivité de la queue (TRE) a immédiatement déclenché plusieurs commentaires sur le dommage que Python ne le fasse pas, y compris des liens vers des entrées de blog récentes par d'autres essayant de "prouver" que TRE peut être ajouté à Python. facilement. Alors laissez-moi défendre ma position (c'est-à-dire que je ne veux pas de TRE dans la langue). Si vous voulez une réponse courte, c'est tout simplement impythonique. Voici la longue réponse:

CPython ne prend pas et ne soutiendra probablement jamais l'optimisation des appels de queue basée sur les déclarations de Guido van Rossum sur le sujet.

J'ai entendu des arguments selon lesquels cela rend le débogage plus difficile en raison de la façon dont il modifie la trace de la pile.

Essayez la mise en œuvre expérimentale du TCO de la macropie pour la taille.

Outre l'optimisation de la récursivité de la queue, vous pouvez définir manuellement la profondeur de récursivité en:

import sys
sys.setrecursionlimit(5500000)
print("recursion limit:%d " % (sys.getrecursionlimit()))