Python是否优化尾部递归？

Question

我有以下代码失败，错误如下：

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，还是我只需要以不同的方式定义它？

Answer 1

Guido这个词在http://neopythonic.blogspot.co.uk/2009/04/tail-recursion-elimination.html

我最近在我的Python历史博客中发布了一篇关于Python功能特性起源的文章。关于不支持尾部递归消除（TRE）的附带评论立即引发了一些关于Python不这样做是多么遗憾的评论，包括其他人试图“证明”TRE可以轻松添加到Python的最近博客条目的链接。所以让我为自己的立场辩护（即我不希望TRE出现在语言中）。如果你想要一个简短的答案，那就是unpythonic。下面是长答案：

Answer 2

我发布了一个执行尾部调用优化（处理尾部递归和延续传递样式）的模块：https://github.com/baruchel/tco

经常有人声称尾递归不适合Pythonic的编码方式，人们不应该关心如何将其嵌入循环中。我不想与这个观点争论；然而，有时出于各种原因，我喜欢尝试或实现新想法作为尾递归函数而不是循环（专注于想法而不是过程，同时在我的屏幕上有20个短函数而不是只有三个“Pythonic”函数，在交互式会话中工作而不是编辑我的代码，等等）。

在Python中优化尾部递归实际上非常容易。虽然据说这是不可能或非常棘手的，但我认为可以通过优雅、简短和通用的解决方案来实现；我甚至认为，这些解决方案中的大多数都不使用Python特性，而应该使用其他特性。干净的lambda表达式与非常标准的循环一起工作，可以为实现尾部递归优化提供快速、高效和完全可用的工具。

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

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

该功能可按以下方式使用：；下面是factorial和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

显然，递归深度不再是一个问题：

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

我认为计算一个表达式，即使是复杂的表达式，也要比计算几个简单表达式快得多，第二个版本就是这样。我没有在我的模块中保留这个新功能，我认为除了“正式”功能外，没有其他情况可以使用它。

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

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

现在所有功能都可以使用了。在以下示例中，对于n的任何正值，将对f（n）求值为单位函数：

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

当然，可以争辩说，异常不打算用于故意重定向解释器（作为一种goto语句，或者可能更确切地说是一种延续传递样式），这是我不得不承认的。但是，我再次发现使用try并将一行作为返回语句的想法很有趣：我们尝试返回某些东西（正常行为），但由于发生了递归调用（异常），我们无法做到这一点。

初步答复（2013-08-29)。

我写了一个非常小的插件来处理尾部递归。你可以在那里找到我的解释：https://groups.google.com/forum/?hl=fr#！主题/comp.lang.python/dIsnJ2BoBKs

它可以将使用尾部递归样式编写的lambda函数嵌入到另一个函数中，该函数将作为循环进行计算。

这个小函数中最有趣的特性，在我的愚见中，是这个函数不依赖于一些肮脏的编程技巧，而是仅仅依赖于lambda演算：当插入另一个lambda函数时，函数的行为会改变为另一个，这看起来非常像Y组合器。

Answer 3

不，而且永远不会，因为吉多·范·罗森更喜欢能够进行适当的追溯：

尾递归消除（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