Tengo el siguiente código que falla con el siguiente error:

RuntimeError: profundidad de recursión máxima excedida

Intenté reescribir esto para permitir la optimización de recursión de cola (TCO). Creo que este código debería haber tenido éxito si se hubiera producido un TCO.

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

print(trisum(1000, 0))

¿Debo concluir que Python no hace ningún tipo de TCO, o solo necesito definirlo de manera diferente?

No, y nunca lo hará, ya que Guido van Rossum prefiere poder tener los rastros adecuados:

Eliminación de recursión de cola (2009-04-22)

Palabras finales sobre llamadas de cola (2009-04-27)

Puede eliminar manualmente la recursividad con una transformación como esta:

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

Publiqué un módulo que realiza la optimización de llamadas de cola (manejando tanto el estilo de recursión de cola como el de paso de continuación): https://github.com/baruchel/tco

Optimizando la recursividad de cola en Python

A menudo se ha afirmado que la recursión de la cola no se adapta a la forma de codificación Pythonic y que a uno no debería importarle cómo incrustarlo en un bucle. No quiero discutir con este punto de vista; a veces, sin embargo, me gusta probar o implementar nuevas ideas como funciones recursivas de la cola en lugar de con bucles por varias razones (centrándome en la idea en lugar del proceso, teniendo veinte funciones cortas en mi pantalla al mismo tiempo en lugar de solo tres "Pythonic" funciones, trabajar en una sesión interactiva en lugar de editar mi código, etc.).

La optimización de la recursividad de cola en Python es, de hecho, bastante fácil. Si bien se dice que es imposible o muy complicado, creo que se puede lograr con soluciones elegantes, cortas y generales; Incluso creo que la mayoría de estas soluciones no usan las características de Python de lo que deberían. Las expresiones lambda limpias que funcionan junto con bucles muy estándar conducen a herramientas rápidas, eficientes y totalmente utilizables para implementar la optimización de recursión de cola.

Como conveniencia personal, escribí un pequeño módulo que implementa tal optimización de dos maneras diferentes. Me gustaría discutir aquí sobre mis dos funciones principales.

La forma limpia: modificar el combinador Y

los combinador Y es bien conocido; permite usar funciones lambda de manera recursiva, pero no permite incrustar llamadas recursivas en un bucle. El cálculo Lambda solo no puede hacer tal cosa. Sin embargo, un ligero cambio en el combinador Y puede proteger la llamada recursiva que se evaluará realmente. Por lo tanto, la evaluación puede retrasarse.

Aquí está la famosa expresión del combinador Y:

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

Con un cambio muy leve, podría obtener:

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

En lugar de llamarse a sí misma, la función f ahora devuelve una función que realiza la misma llamada, pero como la devuelve, la evaluación se puede hacer más tarde desde afuera.

Mi código es:

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 función se puede usar de la siguiente manera; Aquí hay dos ejemplos con versiones recursivas de cola de factorial y 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

Obviamente, la profundidad de recursión ya no es un problema:

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

Por supuesto, este es el único propósito real de la función.

Solo una cosa no se puede hacer con esta optimización: no se puede usar con una función recursiva de cola que evalúa a otra función (esto se debe al hecho de que los objetos devueltos invocables se manejan como llamadas recursivas adicionales sin distinción). Como generalmente no necesito dicha función, estoy muy contento con el código anterior. Sin embargo, para proporcionar un módulo más general, pensé un poco más para encontrar una solución para este problema (consulte la siguiente sección).

En cuanto a la velocidad de este proceso (que no es el problema real sin embargo), resulta ser bastante bueno; las funciones recursivas de cola se evalúan incluso mucho más rápido que con el siguiente código utilizando expresiones más 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

Creo que evaluar una expresión, incluso complicada, es mucho más rápido que evaluar varias expresiones simples, como es el caso en esta segunda versión. No mantuve esta nueva función en mi módulo, y no veo circunstancias en las que pueda usarse en lugar de la "oficial".

Continuar pasando estilo con excepciones

Aquí hay una función más general; es capaz de manejar todas las funciones recursivas de cola, incluidas las que devuelven otras funciones. Las llamadas recursivas se reconocen a partir de otros valores de retorno mediante el uso de excepciones. Esta solución es más lenta que la anterior; un código más rápido probablemente podría escribirse usando algunos valores especiales como "banderas" que se detectan en el bucle principal, pero no me gusta la idea de usar valores especiales o palabras clave internas. Hay alguna interpretación divertida del uso de excepciones: si a Python no le gustan las llamadas recursivas de cola, se debe generar una excepción cuando se produce una llamada recursiva de cola, y la forma pitónica será atrapar la excepción para encontrar algo limpio solución, que en realidad es lo que sucede aquí ...

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

Ahora se pueden usar todas las funciones. En el siguiente ejemplo, f(n)se evalúa la función de identidad para cualquier valor positivo de n:

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

Por supuesto, se podría argumentar que las excepciones no están destinadas a ser utilizadas para redirigir intencionalmente al intérprete (como una especie de gotodeclaración o probablemente como una especie de estilo de paso de continuación), lo cual debo admitir. Pero, de nuevo, me parece graciosa la idea de usar tryuna sola línea como una returndeclaración: tratamos de devolver algo (comportamiento normal) pero no podemos hacerlo debido a una llamada recursiva (excepción).

Respuesta inicial (2013-08-29).

Escribí un complemento muy pequeño para manejar la recursión de cola. Puede encontrarlo con mis explicaciones allí: https://groups.google.com/forum/?hl=fr#!topic/comp.lang.python/dIsnJ2BoBKs

Puede incrustar una función lambda escrita con un estilo de recursión de cola en otra función que la evaluará como un bucle.

La característica más interesante de esta pequeña función, en mi humilde opinión, es que la función no se basa en algún truco de programación sucio sino en un simple cálculo lambda: el comportamiento de la función se cambia a otro cuando se inserta en otra función lambda que se parece mucho al combinador Y.

La palabra de Guido está en http://neopythonic.blogspot.co.uk/2009/04/tail-recursion-elimination.html

Recientemente publiqué una entrada en mi blog de Historia de Python sobre los orígenes de las características funcionales de Python. Una observación al margen sobre no apoyar la eliminación de la recursividad de la cola (TRE) provocó de inmediato varios comentarios sobre la lástima de que Python no haga esto, incluidos los enlaces a las entradas recientes del blog de otros que intentan "probar" que se puede agregar TRE a Python fácilmente. Así que déjame defender mi posición (que es que no quiero TRE en el idioma). Si quieres una respuesta corta, simplemente no es pitónica. Aquí está la respuesta larga:

CPython no admite y probablemente nunca admitirá la optimización de llamadas de cola basadas en Guido van Rossum declaraciones de sobre el tema.

He escuchado argumentos de que dificulta la depuración debido a cómo modifica el seguimiento de la pila.

Pruebe la implementación experimental de macropy TCO para el tamaño.

Además de optimizar la recursividad de la cola, puede establecer la profundidad de recursión manualmente al:

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