¿Python optimiza la recursividad de cola?

recursion stack

Question

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

RuntimeError: se ha excedido la profundidad máxima de recursión

Intenté reescribir esto para permitir la optimización de recursión de cola (TCO). Creo que este código debería haber sido exitoso 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?

Answer 1

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

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

Answer 2

CPython no respalda, y probablemente nunca lo hará, la optimización de las llamadas finales basada en las declaraciones de Guido sobre el tema. He escuchado argumentos que hacen que la depuración sea más difícil debido a la forma en que modifica el seguimiento de la pila.

Answer 3

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. Una observación al margen sobre no apoyar la eliminación de recurrencia de cola (TRE) de inmediato provocó varios comentarios sobre lo lamentable que Python no hace esto, incluyendo enlaces a entradas de blog recientes por parte 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 quieres una respuesta corta, es simplemente antiponónica. Aquí está la respuesta larga:

Answer 4

No, y nunca lo hará, ya que Guido prefiere poder tener los registros correctos

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

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

Puede 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

Answer 5

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

Answer 6

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

Editar (12-07-2015): finalmente publiqué un módulo que realiza la optimización de la cola de llamadas (manejo de la repetición de cola y el estilo de continuación de paso): https://github.com/baruchel/tco

Optimizando la recursión de cola en Python

A menudo se ha afirmado que la recursividad de la cola no se ajusta a la forma de codificación pitónica y que uno no debería preocuparse por cómo incrustarla 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 (enfocándome en la idea más que en el proceso, teniendo veinte funciones cortas en mi pantalla al mismo tiempo en vez de solo tres "pitónicas"). funciones, trabajando en una sesión interactiva en lugar de editar mi código, etc.).

La optimización de la recursividad de la 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 contrario. Las expresiones Clean lambda que funcionan junto con los bucles muy estándar conducen a herramientas rápidas, eficientes y totalmente utilizables para implementar la optimización de recursión de cola.

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

La manera limpia: modificar 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 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. La evaluación se puede retrasar.

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í mismo, la función f ahora devuelve una función que realiza la misma llamada, pero como la devuelve, la evaluación puede realizarse más adelante 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 usar de la siguiente manera; aquí hay dos ejemplos con versiones recursivas 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

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 invocables se manejan como llamadas recursivas adicionales sin distinción). Como normalmente no necesito esa 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 bastante bueno; las funciones recursivas de cola 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 en 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".

Continuación del estilo de pase con excepciones

Aquí hay una función más general; es capaz de manejar todas las funciones recursivas de la 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; un código más rápido probablemente podría escribirse utilizando 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 hacer 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 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 todas las funciones se pueden usar. 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, podría argumentarse que las excepciones no están destinadas a ser utilizadas para redirigir deliberadamente al intérprete (como una especie de declaración goto o probablemente más bien una especie de estilo de continuación de paso), lo que tengo que admitir. Pero, de nuevo, me parece graciosa la idea de usar try con una sola línea que es una declaración de return : tratamos de devolver algo (comportamiento normal) pero no podemos hacerlo debido a una llamada recursiva que ocurre (excepción).

Respuesta inicial (2013-08-29).

Escribí un pequeño complemento 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 recursión de cola en otra función que lo 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 hack de programación sucia sino en el mero 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 Y-combinator.

Saludos.