¿Python optimiza la recursividad de cola?
Tengo el siguiente código que falla con el siguiente error:
RuntimeError: se superó la profundidad máxima de recursividad
Intenté reescribir esto para permitir la optimización de la recursividad final (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 genera ningún tipo de TCO o simplemente necesito definirlo de manera diferente?
No, y nunca lo será, ya que Guido van Rossum prefiere poder tener rastreos adecuados:
Eliminación de recursividad de cola (22 de abril de 2009)
Palabras finales sobre llamadas de cola (2009-04-27)
Puedes 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 recursividad de cola como el de paso de continuación): https://github.com/baruchel/tco
Optimización de la recursividad de cola en Python
A menudo se ha afirmado que la recursividad de cola no se adapta a la forma de codificación Pythonic y que no debería preocuparse por 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 cola en lugar de bucles por varias razones (centrándome en la idea más que en el 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.).
De hecho, optimizar la recursividad de cola en Python es 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 utilizan las funciones de Python de otra manera de lo que deberían. Las expresiones lambda limpias que funcionan junto con bucles muy estándar generan herramientas rápidas, eficientes y totalmente utilizables para implementar la optimización de la recursividad de cola.
Para comodidad personal, escribí un pequeño módulo que implementa dicha optimización de dos maneras diferentes. Me gustaría hablar aquí sobre mis dos funciones principales.
La forma limpia: modificando el combinador Y
El combinador Y es bien conocido; permite utilizar funciones lambda de forma recursiva, pero no permite por sí solo incrustar 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 Y puede proteger la llamada recursiva para que sea realmente evaluada. Por 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 muy ligero cambio, 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 realizar más tarde desde fuera.
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 recursividad 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.
Sólo 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 todos los objetos devueltos invocables se manejan como llamadas recursivas adicionales sin distinción). Como normalmente 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 alguna solución a este problema (consulte la siguiente sección).
En cuanto a la velocidad de este proceso (que no es el verdadero problema), resulta ser bastante buena; Las funciones recursivas de cola se evalúan incluso 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 complicada, es mucho más rápido que evaluar varias expresiones simples, como es el caso de esta segunda versión. No mantuve esta nueva función en mi módulo y no veo ninguna circunstancia en la que pueda usarse en lugar de la "oficial".
Estilo de pase de continuación 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 a partir de otros valores de retorno mediante el uso de excepciones. Esta solución es más lenta que la anterior; Probablemente se podría escribir un código más rápido 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 una interpretación curiosa del uso de excepciones: si a Python no le gustan las llamadas recursivas de cola, se debe generar una excepción cuando se produzca una llamada recursiva de cola, y la forma Pythonic será detectar la excepción para encontrar algo limpio. solución, que es en realidad 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 utilizar 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 redirigir intencionalmente al intérprete (como una especie de gotodeclaración o probablemente más bien una especie de estilo de paso de continuación), lo cual debo admitir. Pero, nuevamente, encuentro divertida la idea de usar tryuna sola línea como returndeclaración: intentamos devolver algo (comportamiento normal) pero no podemos hacerlo debido a que ocurre una llamada recursiva (excepción).
Respuesta inicial (29-08-2013).
Escribí un complemento muy pequeño para manejar la recursividad de cola. Puedes 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 ningún truco de programación sucio 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 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. Un comentario adicional sobre no admitir la eliminación de recursividad de cola (TRE) inmediatamente provocó varios comentarios sobre lo lamentable que es que Python no haga esto, incluidos enlaces a entradas de blog recientes de otros que intentaban "probar" que TRE se puede agregar a Python. fácilmente. Permítanme defender mi posición (que es que no quiero TRE en el idioma). Si desea una respuesta breve, es simplemente poco pitónica. Aquí está la respuesta larga:
