问题描述：

我有以下一段代码，它因以下错误而失败：

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，或者我只需要对其进行不同的定义？

解决方案 1：

不，而且永远不会，因为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

解决方案 2：

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

在 Python 中优化尾递归

人们经常说尾递归不适合 Pythonic 编码方式，人们不应该关心如何将其嵌入循环中。我不想与这种观点争论；但有时我喜欢尝试或实现新想法作为尾递归函数，而不是循环，原因有很多（专注于想法而不是过程，屏幕上同时显示 20 个简短函数，而不是只有三个“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：我们尝试返回某些内容（正常行为），但由于发生了递归调用（异常），我们无法做到这一点。

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

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

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

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

解决方案 3：

Guido 的话可以在http://neopythonic.blogspot.co.uk/2009/04/tail-recursion-elimination.html找到。

我最近在我的 Python 历史博客中发布了一篇关于 Python 函数式特性起源的文章。关于不支持尾递归消除 (TRE) 的附带评论立即引发了多条评论，称 Python 不支持尾递归消除真是可惜，其中包括其他人试图“证明”可以轻松将 TRE 添加到 Python 的最新博客文章链接。所以，让我捍卫我的立场（即我不希望语​​言中包含 TRE）。如果您想要一个简短的答案，那就是它根本不符合 Python 风格。下面是详细答案：

解决方案 4：

根据Guido van Rossum关于此主题的陈述，CPython不支持尾部调用优化，并且可能永远不会支持。

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

解决方案 5：

尝试实验性的macropy TCO 实现尺寸。

解决方案 6：

在 Python 中，尾部调用永远无法优化为跳转。优化是一种保留程序含义的程序转换。尾部调用消除不会保留 Python 程序的含义。

经常提到的一个问题是尾调用消除会改变调用堆栈，而 Python 允许在运行时检查堆栈。但还有一个很少被提及的问题。可能有很多这样的代码：

def map_file(path):
    f = open(path, 'rb')
    return mmap.mmap(f.fileno())

对 的调用mmap.mmap位于尾部位置。如果将其替换为跳转，则在将控制权传递给 之前，当前堆栈帧将被丢弃mmap。当前堆栈帧包含对文件对象的唯一引用，因此文件对象可以在 调用之前释放（在 CPython 中会释放）mmap，这将关闭文件描述符，在mmap看到它之前使其无效。

最好的情况是，代码会因异常而失败。最坏的情况是，文件描述符可能会在另一个线程中重用，从而导致mmap映射错误的文件。因此，这种“优化”对于大量现有的 Python 代码来说可能是一种灾难性的后果。

Python 规范保证不会发生此类问题，因此您可以确保没有任何符合要求的实现会转换return f(args)为跳转 - 除非它有一个复杂的静态分析引擎，可以证明在这种情况下提前丢弃对象不会产生可观察到的后果。

这些都不会阻止 Python 添加具有跳转语义的显式尾调用语法，例如

    return from f(args)

这不会破坏未使用它的代码，并且它可能对自动生成的代码和某些算法有用。GvR 不再是 BDFL，所以这可能会发生，但我不会屏住呼吸。

解决方案 7：

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 上的页面（俄语，抱歉）上阅读一些重要的限制。但是，此解决方案非常“真实”，不会中断代码和其他类似的技巧。

解决方案 8：

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

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