¿Python optimiza la recursión de la cola?

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

RuntimeError: profundidad de recursión máxima excedida

Intenté volver a escribir esto para permitir la optimización de la recursión de la 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 realiza ningún tipo de TCO, o simplemente necesito definirlo de manera diferente?

No, y nunca lo hará, ya que Guido prefiere tener las respuestas correctas.

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

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

Puedes eliminar manualmente la recursión 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 

Editar (2015-07-02): Con el tiempo, mi respuesta se ha vuelto bastante popular y, dado que inicialmente era más un enlace que cualquier otra cosa, decidí tomarme un tiempo y reescribirlo por completo (sin embargo, la respuesta inicial puede se encuentra al final).

Edición (2015-07-12): Finalmente publiqué un módulo que realizaba 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 recursión de cola en Python

A menudo se ha afirmado que la recursión de la cola no se adapta a la forma pythonica de encoding y que no debería importarse cómo incrustarla en un bucle. No quiero discutir este punto de vista; A veces, sin embargo, me gusta probar o implementar nuevas ideas como funciones recursivas de cola en lugar de bucles por varias razones (centrándose en la idea en lugar de en el proceso, tener veinte funciones cortas en mi pantalla al mismo tiempo en lugar de solo tres “pythonic” funciones, trabajando en una sesión interactiva en lugar de editar mi código, etc.).

La optimización de la recursión 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, breves y generales; Incluso creo que la mayoría de estas soluciones no usan las características de Python de lo contrario. Las expresiones lambda limpias que funcionan junto con bucles muy estándar llevan a herramientas rápidas, eficientes y totalmente utilizables para implementar la optimización de la recursión de la cola.

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

La forma limpia: modificando el combinador Y

El combinador Y es bien conocido; permite utilizar las funciones lambda de manera recursiva, pero no permite integrar llamadas recursivas en un bucle. El cálculo lambda por sí solo no puede hacer tal cosa. Sin embargo, un ligero cambio en el combinador de Y puede proteger la llamada recursiva para que se evalúe realmente. La evaluación puede retrasarse.

Aquí está la famosa expresión para el combinador de Y:

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

Con un cambio muy leve, pude conseguir:

 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 el exterior.

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 utilizar 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 la recursión ya no es un problema:

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

Este es, por supuesto, el único propósito real de la función.

Solo se puede hacer una cosa con esta optimización: no se puede usar con una función recursiva de cola que evalúe a otra función (esto se debe al hecho de que los objetos devueltos que se pueden llamar se manejan como llamadas recursivas adicionales sin distinción). Ya que normalmente no necesito tal característica, 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 alguna solución para este problema (ver 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 incluso se evalúan mucho más rápido que con el siguiente código usando 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 si es complicado, 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 ninguna circunstancia en la que se pueda usar en lugar de la “oficial”.

Continuación de pases estilo con excepciones.

Aquí hay una función más general; es capaz de manejar todas las funciones recursivas de cola, incluidas aquellas que devuelven otras funciones. Las llamadas recursivas se reconocen de otros valores de retorno mediante el uso de excepciones. Esta solución es más lenta que la anterior; probablemente se pueda escribir un código más rápido utilizando algunos valores especiales como “indicadores” que se detectan en el ciclo principal, pero no me gusta la idea de usar valores especiales o palabras clave internas. Hay una interpretación divertida del uso de excepciones: si a Python no le gustan las llamadas recursivas de cola, debe producirse una excepción cuando se produce una llamada recursiva de cola, y la forma pythonica será capturar la excepción para encontrar algo limpio. solución, que en realidad es lo que pasa 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 utilizar todas las funciones. En el siguiente ejemplo, f(n) se evalúa en 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 tienen la intención de ser usadas para redirigir intencionalmente al intérprete (como un tipo de statement de goto o probablemente más bien como un tipo de estilo de paso de continuación), que debo admitir. Pero, nuevamente, me parece graciosa la idea de usar try con una sola línea como una statement de return : intentamos devolver algo (comportamiento normal) pero no podemos hacerlo debido a una llamada recursiva (excepción).

Respuesta inicial (2013-08-29).

Escribí un plugin muy pequeño para manejar la recursión de la 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 un poco de progtwigción sucia sino en un mero cálculo lambda: el comportamiento de la función cambia a otro cuando se inserta en otra función lambda que se parece mucho al combinador en Y.

Saludos.

La palabra de Guido se encuentra 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 funciones funcionales de Python. Una observación lateral sobre no apoyar la eliminación de la recursión de la cola (TRE) provocó de inmediato varios comentarios sobre la pena que Python no hace esto, incluidos los enlaces a entradas de blog recientes 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, es simplemente anti-tónica. Aquí está la respuesta larga:

CPython no lo hace y probablemente nunca apoyará la optimización de llamadas basadas en las declaraciones de Guido sobre el tema. He escuchado argumentos que hacen que la depuración sea más difícil debido a cómo modifica el seguimiento de la stack.

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

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

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