Python是否优化尾部递归?

问题:Python是否优化尾部递归?

我有以下代码,失败并出现以下错误:

RuntimeError:超过最大递归深度

我试图重写此代码以允许尾递归优化(TCO)。我相信,如果发生了TCO,则该代码应该会成功。

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

print(trisum(1000, 0))

我是否应该得出结论,Python不执行任何类型的TCO,还是只需要以不同的方式定义它?

I have the following piece of code which fails with the following error:

RuntimeError: maximum recursion depth exceeded

I attempted to rewrite this to allow for tail recursion optimization (TCO). I believe that this code should have been successful if a TCO had taken place.

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

print(trisum(1000, 0))

Should I conclude that Python does not do any type of TCO, or do I just need to define it differently?


回答 0

不,而且永远不会,因为Guido van Rossum希望能够进行适当的追溯:

消除尾递归(2009-04-22)

尾声定语(2009-04-27)

您可以通过以下转换手动消除递归:

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

No, and it never will since Guido van Rossum prefers to be able to have proper tracebacks:

Tail Recursion Elimination (2009-04-22)

Final Words on Tail Calls (2009-04-27)

You can manually eliminate the recursion with a transformation like this:

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

回答 1

我发布了执行尾部调用优化的模块(处理尾部递归和连续传递样式):https : //github.com/baruchel/tco

在Python中优化尾递归

经常有人声称尾递归不适合Pythonic的编码方式,而且人们不应该在意如何将其嵌入循环中。我不想以这种观点参数。但是有时我还是喜欢尝试或将新的想法作为尾递归函数而不是由于各种原因而使用循环(出于各种原因(着眼于想法而不是过程,同时在屏幕上同时具有二十个短函数,而不是三个“ Pythonic”)功能,在交互式会话中工作而不是编辑我的代码等)。

实际上,在Python中优化尾递归非常容易。尽管据说这是不可能的或非常棘手的,但我认为可以通过优雅,简短和通用的解决方案来实现。我什至认为这些解决方案中的大多数都没有使用Python功能,而是应该使用它们。干净的lambda表达式与非常标准的循环一起使用,可以快速,高效且完全可用的工具来实现尾递归优化。

为了个人方便,我编写了一个小模块,通过两种不同的方式来实现这种优化。我想在这里讨论我的两个主要功能。

干净的方法:修改Y组合器

Y组合是公知的; 它允许以递归方式使用lambda函数,但它本身不允许将递归调用嵌入循环中。单凭Lambda演算就无法做到这一点。但是,Y组合器中的微小变化可以保护递归调用被实际评估。因此可以延迟评估。

这是Y组合器的著名表达:

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

进行很小的更改,我可以得到:

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

现在,函数f不再调用自身,而是返回执行相同调用的函数,但是由于返回了函数,因此可以稍后从外部进行评估。

我的代码是:

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

该功能可以通过以下方式使用:这是阶乘和斐波那契的尾递归版本的两个示例:

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

显然,递归深度不再是一个问题:

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

当然,这是该功能的唯一实际目的。

此优化只能完成一件事情:不能与评估另一个函数的尾部递归函数一起使用(这是由于可调用返回的对象都被当作没有区别的进一步递归调用来处理的事实)。由于我通常不需要这种功能,因此我对上面的代码感到非常满意。但是,为了提供一个更通用的模块,我想了一下,以便找到解决此问题的方法(请参阅下一节)。

关于这个过程的速度(但这不是真正的问题),它碰巧是相当不错的。尾递归函数甚至比使用以下代码使用更简单的表达式更快地求值:

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

我认为评估一个甚至复杂的表达式比评估几个简单的表达式要快得多,第二个版本就是这种情况。我没有在模块中保留此新功能,而且在任何情况下都不能使用它而不是“官方”功能。

延续传球方式,但有exceptions

这是一个更通用的功能;它能够处理所有的尾递归函数,包括那些返回其他函数的函数。通过使用异常,可以从其他返回值中识别出递归调用。这种解决方案比以前的解决方案要慢。通过在主循环中检测到一些特殊值作为“标志”,可以编写更快的代码,但是我不喜欢使用特殊值或内部关键字的想法。使用异常有一些有趣的解释:如果Python不喜欢尾递归调用,那么当确实发生尾递归调用时,应该引发一个异常,而Python的方式将是捕获该异常以找到一些干净的方法解决方案,这实际上就是这里发生的事情…

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

现在可以使用所有功能。在以下示例中,f(n)对n的任何正值求值到恒等函数:

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

当然,可以争辩说,异常并非旨在用于故意重定向解释器(作为一种goto陈述,或者可能是一种延续传递样式),我必须承认。但是,再次让我觉得有趣的是使用try单行作为return语句的想法:我们尝试返回某些内容(正常行为),但是由于发生递归调用(异常)而无法这样做。

初步答案(2013-08-29)。

我写了一个很小的插件来处理尾递归。您可以在这里找到我的解释:https//groups.google.com/forum/?hl = fr#!topic / comp.lang.python / dIsnJ2BoBKs

它可以将以尾部递归样式编写的lambda函数嵌入另一个函数中,该函数会将其评估为循环。

以我的拙见,这个小函数最有趣的功能是该函数不依赖于肮脏的编程技巧,而仅依赖于lambda演算:插入另一个lambda函数后,该函数的行为会更改为另一个行为。看起来非常像Y组合器。

I published a module performing tail-call optimization (handling both tail-recursion and continuation-passing style): https://github.com/baruchel/tco

Optimizing tail-recursion in Python

It has often been claimed that tail-recursion doesn’t suit the Pythonic way of coding and that one shouldn’t care about how to embed it in a loop. I don’t want to argue with this point of view; sometimes however I like trying or implementing new ideas as tail-recursive functions rather than with loops for various reasons (focusing on the idea rather than on the process, having twenty short functions on my screen in the same time rather than only three “Pythonic” functions, working in an interactive session rather than editing my code, etc.).

Optimizing tail-recursion in Python is in fact quite easy. While it is said to be impossible or very tricky, I think it can be achieved with elegant, short and general solutions; I even think that most of these solutions don’t use Python features otherwise than they should. Clean lambda expressions working along with very standard loops lead to quick, efficient and fully usable tools for implementing tail-recursion optimization.

As a personal convenience, I wrote a small module implementing such an optimization by two different ways. I would like to discuss here about my two main functions.

The clean way: modifying the Y combinator

The Y combinator is well known; it allows to use lambda functions in a recursive manner, but it doesn’t allow by itself to embed recursive calls in a loop. Lambda calculus alone can’t do such a thing. A slight change in the Y combinator however can protect the recursive call to be actually evaluated. Evaluation can thus be delayed.

Here is the famous expression for the Y combinator:

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

With a very slight change, I could get:

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

Instead of calling itself, the function f now returns a function performing the very same call, but since it returns it, the evaluation can be done later from outside.

My code is:

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

The function can be used in the following way; here are two examples with tail-recursive versions of factorial and 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

Obviously recursion depth isn’t an issue any longer:

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

This is of course the single real purpose of the function.

Only one thing can’t be done with this optimization: it can’t be used with a tail-recursive function evaluating to another function (this comes from the fact that callable returned objects are all handled as further recursive calls with no distinction). Since I usually don’t need such a feature, I am very happy with the code above. However, in order to provide a more general module, I thought a little more in order to find some workaround for this issue (see next section).

Concerning the speed of this process (which isn’t the real issue however), it happens to be quite good; tail-recursive functions are even evaluated much quicker than with the following code using simpler expressions:

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

I think that evaluating one expression, even complicated, is much quicker than evaluating several simple expressions, which is the case in this second version. I didn’t keep this new function in my module, and I see no circumstances where it could be used rather than the “official” one.

Continuation passing style with exceptions

Here is a more general function; it is able to handle all tail-recursive functions, including those returning other functions. Recursive calls are recognized from other return values by the use of exceptions. This solutions is slower than the previous one; a quicker code could probably be written by using some special values as “flags” being detected in the main loop, but I don’t like the idea of using special values or internal keywords. There is some funny interpretation of using exceptions: if Python doesn’t like tail-recursive calls, an exception should be raised when a tail-recursive call does occur, and the Pythonic way will be to catch the exception in order to find some clean solution, which is actually what happens here…

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

Now all functions can be used. In the following example, f(n) is evaluated to the identity function for any positive value of n:

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

Of course, it could be argued that exceptions are not intended to be used for intentionally redirecting the interpreter (as a kind of goto statement or probably rather a kind of continuation passing style), which I have to admit. But, again, I find funny the idea of using try with a single line being a return statement: we try to return something (normal behaviour) but we can’t do it because of a recursive call occurring (exception).

Initial answer (2013-08-29).

I wrote a very small plugin for handling tail recursion. You may find it with my explanations there: https://groups.google.com/forum/?hl=fr#!topic/comp.lang.python/dIsnJ2BoBKs

It can embed a lambda function written with a tail recursion style in another function which will evaluate it as a loop.

The most interesting feature in this small function, in my humble opinion, is that the function doesn’t rely on some dirty programming hack but on mere lambda calculus: the behaviour of the function is changed to another one when inserted in another lambda function which looks very like the Y combinator.


回答 2

Guido的字词位于http://neopythonic.blogspot.co.uk/2009/04/tail-recursion-elimination.html

我最近在我的Python历史记录博客中发布了有关Python功能特性起源的条目。关于不支持尾递归消除(TRE)的附带评论立即引发了一些评论,说明Python不能做到这一点是多么可惜,包括其他人试图“证明”可以将TRE添加到Python的最新博客条目的链接。容易。因此,让我捍卫自己的立场(这就是我不希望使用该语言的TRE)。如果您想要一个简短的答案,那简直就是不可思议。这是很长的答案:

The word of Guido is at http://neopythonic.blogspot.co.uk/2009/04/tail-recursion-elimination.html

I recently posted an entry in my Python History blog on the origins of Python’s functional features. A side remark about not supporting tail recursion elimination (TRE) immediately sparked several comments about what a pity it is that Python doesn’t do this, including links to recent blog entries by others trying to “prove” that TRE can be added to Python easily. So let me defend my position (which is that I don’t want TRE in the language). If you want a short answer, it’s simply unpythonic. Here’s the long answer:


回答 3

CPython不会并且可能永远不会基于Guido van Rossum关于该主题陈述来支持尾部调用优化。

我听说过有论点,因为它如何修改堆栈跟踪,这使调试更加困难。

CPython does not and will probably never support tail call optimization based on Guido van Rossum’s statements on the subject.

I’ve heard arguments that it makes debugging more difficult because of how it modifies the stack trace.


回答 4

尝试使用实验性 TCO实施以获取大小。

Try the experimental macropy TCO implementation for size.


回答 5

除了优化尾递归,您还可以通过以下方式手动设置递归深度:

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

Besides optimizing tail recursion, you can set the recursion depth manually by:

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