250

我有以下一段代码失败并出现以下错误：

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

4

7 回答 7

266

不，它永远不会，因为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
于 2012-11-27T19:55:43.597 回答
201

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

在 Python 中优化尾递归

人们经常声称尾递归不适合 Pythonic 的编码方式，并且不应该关心如何将其嵌入循环中。我不想与这种观点争论；但有时我喜欢尝试或实现新想法作为尾递归函数而不是循环，原因有很多（专注于想法而不是过程，在我的屏幕上同时有 20 个短函数，而不是只有 3 个“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 不喜欢尾递归调用，当发生尾递归调用时应该引发异常，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 组合器。

于 2013-08-29T09:08:18.580 回答
23

Guido 的话在http://neopythonic.blogspot.co.uk/2009/04/tail-recursion-elimination.html

我最近在我的 Python 历史博客上发表了一篇关于 Python 函数特性起源的文章。一个关于不支持尾递归消除 (TRE) 的评论立即引发了几条评论，说 Python 不这样做是多么遗憾，包括其他人试图“证明” TRE 可以添加到 Python 的最近博客条目的链接容易地。因此，让我捍卫我的立场（即我不希望在语言中使用 TRE）。如果您想要一个简短的答案，那简直是无稽之谈。这是长答案：

于 2012-11-27T19:56:53.020 回答
8

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

我听说过它使调试变得更加困难的论点，因为它修改了堆栈跟踪。

于 2012-11-27T19:55:40.307 回答
5

除了优化尾递归之外，您还可以通过以下方式手动设置递归深度：

import sys
sys.setrecursionlimit(5500000)
print("recursion limit:%d " % (sys.getrecursionlimit()))
于 2016-06-09T14:38:23.510 回答
4

尝试使用实验性的macropy TCO 实现来确定大小。

于 2015-07-15T00:11:30.557 回答
2

Python 中没有内置的尾递归优化。但是，我们可以通过抽象语法树（AST）“重建”函数，消除那里的递归并用循环替换它。Guido 是绝对正确的，这种方法有一些局限性，所以我不推荐使用它。

但是，我仍然编写（而不是作为训练示例）我自己的优化器版本，您甚至可以尝试它是如何工作的。

通过 pip 安装这个包：

pip install astrologic

现在您可以运行此示例代码：

from astrologic import no_recursion

counter = 0

@no_recursion
def recursion():
    global counter
    counter += 1
    if counter != 10000000:
        return recursion()
    return counter

print(recursion())

这个解决方案不稳定，你永远不应该在生产中使用它。您可以在 github上阅读有关页面上的一些重要限制（俄语，抱歉）。然而，这个解决方案是相当“真实”的，没有中断代码和其他类似的技巧。

于 2021-03-20T03:40:07.160 回答