Ya no tienes que buscar más por internet ya que estás al lugar correcto, poseemos la solución que quieres hallar y sin complicaciones.
Solución:
No, y nunca lo será, ya que Guido van Rossum prefiere poder tener rastreos adecuados:
Eliminación de la recursividad de la 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 la llamada de cola (que maneja 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 la cola en Python
A menudo se ha afirmado que la recursividad de la cola no se adapta a la forma de codificación Pythonic y que no debería preocuparse por cómo insertarla 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 con bucles por varias razones (centrándome en la idea en lugar del proceso, tener 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 la cola en Python es bastante fácil. Si bien se dice que es imposible o muy engañoso, creo que se puede lograr con soluciones elegantes, breves y generales; Incluso creo que la mayoría de estas soluciones no usan las funciones de Python de otra manera 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 recursividad de cola.
Como conveniencia personal, escribí un pequeño módulo que implementa dicha optimización de dos maneras diferentes. Me gustaría discutir aquí sobre mis dos funciones principales.
La forma limpia: modificando el combinador Y
El combinador Y es bien conocido; permite usar funciones lambda de manera recursiva, pero no permite por sí mismo 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 se evalúe realmente. 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 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 el exterior.
Mi codigo 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 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.
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 proviene del hecho de que los objetos devueltos invocables se manejan como llamadas recursivas adicionales sin distinción). Como normalmente no necesito esta 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 para este problema (consulte la siguiente sección).
Con respecto 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 complicada, es mucho más rápido que evaluar varias expresiones simples, como es el caso de esta segunda versión. No guardé esta nueva función en mi módulo, y no veo circunstancias en las 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 las que devuelven otras funciones. Las llamadas recursivas se reconocen a partir de otros valores devueltos 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 una 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 ocurra una llamada recursiva de cola, y la forma Pythonic será capturar 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 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 goto declaración o probablemente más bien una especie de estilo de continuación de paso), que tengo que admitir. Pero, de nuevo, encuentro divertida la idea de usar try con una sola línea que es un return declaración: intentamos devolver algo (comportamiento normal) pero no podemos hacerlo porque se produce una llamada recursiva (excepción).
Respuesta inicial (2013-08-29).
Escribí un complemento muy pequeño para manejar la recursividad 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 recursividad 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 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 Python History sobre los orígenes de las características funcionales de Python. Un comentario lateral sobre no admitir la eliminación de recursividad de cola (TRE) provocó inmediatamente varios comentarios sobre la lástima que Python no haga esto, incluidos enlaces a entradas de blog recientes de otros que intentan “probar” que TRE se puede agregar a Python fácilmente. Así que déjame defender mi posición (que es que no quiero TRE en el idioma). Si desea una respuesta breve, simplemente no es pitónica. Aquí está la respuesta larga: