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

你可以通过这样的转换来手动消除递归

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

在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

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

延续传球方式，但有例外

这是一个更通用的功能；它能够处理所有的尾递归函数，包括那些返回其他函数的函数。通过使用异常，可以从其他返回值中识别出递归调用。这种解决方案比以前的解决方案要慢。可以通过使用一些特殊值（例如在主循环中检测到“标志”）来编写更快的代码，但是我不喜欢使用特殊值或内部关键字的想法。使用异常有一些有趣的解释：如果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

现在可以使用所有功能。在以下示例中，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语句的想法很有趣：我们尝试返回某些内容（正常行为），但是由于递归调用的出现（异常）而无法这样做。