原作者：Guido
原文地址
我最近在 Python 之历史博客中发布了一篇关于 Python “函数式” 起源 的文章。“不支持尾递归消除（TRE）”这一句话带来了类似 “很遗憾 Python 不会这么做” 的评论，以及尝试 “证明” TRE 可以容易地添加到 Python 中的博客。那么让我捍卫自己的立场：我不希望 Python 有 TRE。一个简短的答案就是 TRE 一点也不 Pythonic。 下面是长答案：
首先，正如一位评论者所言，TRE 与优雅的栈跟踪信息是不相容的：尾部递归被消除后，若出现错误，没有任何堆栈框架可用于打印回溯。这会混淆那些无意中使用递归的用户（递归在打印的栈跟踪中不明显），并且使调试变得困难。提供一个禁用 TRE 的选项对我来说是错误的：Python 的默认值应该总是对调试最有帮助。这也让我能提出接下的事情。
其次，TRE 仅仅是一种优化，每个 Python 实现都可以选择实现或不实现的想法是错误的。一旦存在尾递归消除，开发人员将开始编写依赖于它的代码，并且他们的代码将无法在没有提供 TRE 的实现上运行：典型的 Python 实现允许 1000 次递归，这对于非递归或用于递归遍历的代码是足够的，例如，一个经典的解析树，但不足以用于递归遍历一个大的列表。
第三，我不相信递归是所有编程的基础。这是某些计算机科学家的基本信念，特别是那些热爱 Scheme 并喜欢以 cons 单元和递归作为编程教程开头的人。但对我而言，将递归看作是所有其他事物的基础只是一个很好的理论方法，而不是日常的工具。
出于实际的目的，对于刚开始探索编程世界来说，Python 风格的列表（它们是灵活的数组，而不是链表），以及一般的序列，比递归更有用。对于有经验的 Python 程序员来说，它们也是最重要的工具。使用链表来表示序列显然是不够 Pythonic，同时在大多数情况下效率非常低。 Python 的大部分库都是用序列和迭代器作为基本构建块（当然还有词典）编写的，而不是链表，所以不使用列表或序列你将无法享受许多预定义的实用功能。
最后，让我们看看如何实现尾递归消除。第一个值得注意的是你不能在编译时这么做。我已经看到至少有一个博客利用字节码在 RETURN 操作之前替换 CALL操作，改为跳转到函数体的顶部。这可能是一个很好的演示，但不幸的是，Python 的编译器不能可靠地确定任何特定的调用是否实际上引用了当前函数，即使它看起来具有相同的名称。考虑这个简单的例子：
def f(x):
if x > 0:
return f(x-1)
return 0
看起来你可以用这样的东西替换函数体：
if x > 0:
x = x-1
# <跳转到顶部>
return 0
这似乎很简单，但现在添加：
g = f
def f(x):
return x
g(5)
调用 g(5) 时用到了前一个f，但“递归”调用不再递归！在运行时，名字 f 被再绑定到后面的非递归定义的版本，所以返回的值是 4，而不是 0。虽然我同意这个例子是不好的风格，但它是 Python 明确定义的语义，具有大量合法用途。一个编译器如果乐观地认为 f 的定义保持不变，会因这种替换在现实世界的代码中导致令人发指的错误。
另一篇博客展示了可用于使用神奇异常或返回值实现尾递归的装饰器。这些可以用普通的 Python 编写（尽管这篇文章展示了一个优化的 Cython 版本，声称它“速度只慢了10％”，尽管它似乎不是线程安全的）。如果这让你想去使用，我不会试图阻止你，但我强烈反对在核心发行版中包含这样的内容：使用这样的装饰器有许多警告，因为它必须假定任何递归调用（在装饰函数中）是尾递归的并且可以被消除。在经验不足的用户手中，这很容易导致灾难。例如，阶乘的通用递归定义不是尾递归的：
def fact(n):
if n > 1:
return n * fact(n-1)
return 1
还有有很多函数包含一个尾递归调用和另一个不是尾递归的递归调用，装饰器不处理这种情况。这些装饰器无法处理的另一个微妙之处是在 try 块内部进行尾递归调用：这些调用块可能看起来像可以被删除，但它们不能，因为 TRE 可以删除由语言保证的异常处理。由于所有这些原因，我认为这个方法是糟糕的，至少对于一般的用户来说。
但是，如果有人决定将 TRE 添加到 CPython，他们可以大致如下修改编译器。首先，确定“安全”尾递归呼叫站点。这就像是一个 CALL 操作码，紧跟着一个 RETURN 操作码，并且完全在任何 try 块之外。（注意：我忽略了不同的 CALL_ *操作码，这应该很容易使用相同的方法处理。）接下来，用一个 CALL_RETURN 操作码替换每个这样的 CALL - RETURN 操作码对。编译器不需要尝试检查被调用函数的名称是否与当前函数相同：只需通过节省解码第二个操作码的时间，新操作码就可以节省所有 CALL + RETURN 组合的成本。如果在运行时确定此特定调用不适用于 TRE，则执行 CALL 和 RETURN 操作码之后的通常操作。（我想你可以添加一些对调用位点索引过缓存机制来加速运行时间的决定。）
在确定可以优化时，可以设置几种优化级别。如果被调用的对象是已经在当前栈帧中运行的函数，那么最不积极的 vanilla 方法将只优化调用。我们现在要做的就是清除当前堆栈框架中的局部（以及其他隐藏状态，例如活动循环），设置赋值栈中的参数并跳转到函数顶部。 （微妙地，根据定义，新的参数在当前的堆栈中。可能只是需要先复制它们，更微妙的是关键字参数，可变长度参数列表和默认参数值的存在。虽然这只是一个简单的编程问题。）
一个更激进的版本也将识别出一种方法是尾递归的情况（即被调用的对象是一个方法，其底层函数与当前栈帧中的函数相同）。这只需要更多的编程；CPython 解释器代码（ceval.c）已经对方法调用进行了优化。（我不知道这将是多么有用：我期望尾部递归风格受到喜欢使用函数式编程风格的程序员的欢迎，并且可能不会使用太多的类。)
从理论上讲，只要新调用所需的局部变量的数量可以在当前堆栈框架对象中调节，就可以优化所有被调用的对象是用 Python 编写的函数或方法的情况。（CPython中的Frame对象被分配到堆上，并且具有基于本地所需空间的变量分配大小;已经有用于重用框架对象的机器）。这将优化相互的尾递归函数，否则将不会是优化。唉，它也会在大多数情况下禁用堆栈跟踪，所以它可能不是一个好主意。
一个更好的变体是像以前一样创建 Python 级别的堆栈对象，但重用 C 堆栈框架。这将创建一个近似无栈的 Python，尽管递归内置的函数或方法，仍然可以很容易地耗尽 C 的堆栈。
当然，这些都不能解决我的前三个问题。重写你的函数来使用循环是否真的是一件大事？（毕竟 TRE 只处理可以很容易被循环替换的递归）
