Python 不支持尾递归的原因

小甲鱼

Python 不支持尾递归的原因

尾递归是一种特殊形式的递归，其中函数的最后一个操作是对自身的递归调用。

这种方式的优势在于，如果编程语言的编译器或解释器能够进行尾递归优化（Tail Call Optimization，即 TCO）

那么它就可以在常数级的空间复杂度下执行，而不会像常规递归那样随着递归深度的增长而消耗更多内存。

不过，可惜的是 Python 并不支持尾递归（也就是 CPython 并没有针对尾递归代码进行任何优化）。

Python 的设计者 Guido van Rossum 曾经在一篇名为 “Tail Recursion Elimination” 的文章中给出了不支持尾递归优化的一些理由：

• 可读性和透明性：Guido van Rossum 指出 Python 的设计哲学之一是代码应当易于人类理解。尾递归优化会使得函数调用栈变得模糊，因为优化后的调用栈会丢失原始递归过程的一些信息。
• 调试难度： 尾递归优化可能会使调试变得更加困难，因为如果出现错误，堆栈跟踪可能无法提供足够的信息来确定问题发生在哪一层的递归调用中。
• Pythonic 方式： 在 Python 中，迭代通常是首选的处理大量数据的方式，而不是递归。Python 有很多内置的迭代工具，比如生成器和列表推导式，这些工具在处理大规模数据时往往更加有效。
  

以下是 Guido van Rossum 的原文翻译：


消除尾递归优化

最近在我的 Python 历史博客中发表了一篇 关于 Python 功能特性起源 的文章

一个关于不支持尾递归优化（TRE）的侧面评论立即引发了几条评论，其中包括对 Python 不实现这一点表示遗憾的言论，以及其他人试图 “证明” 可以轻松地将 TRE 添加到 Python 中的最新博客条目的链接。

因此，让我来为我的立场辩护（那就是我不希望在语言中有 TRE）。如果你想要一个简短的答案，那就是 —— 这样做完全不符合 Python 的风格。

以下是详细的解释：

首先，正如一位评论者所说，TRE 与清晰的堆栈追踪是不兼容的：当一个尾递归被消除后，将没有剩余的堆栈帧可以用来在后续出错时打印追踪信息。

这会让那些不小心写出了递归代码的用户（在打印的堆栈追踪中递归并不明显）感到困惑，并使得调试变得困难。

提供一个选项来禁用 TRE 在我看来是错误的：Python 的默认设置应该总是尽可能地方便调试。

这也引出了我接下来要讨论的问题……


其次，认为 TRE 只是一种优化，每个 Python 实现可以选择是否实现它，是错误的。

一旦存在尾递归优化，开发人员就会开始编写依赖于它的代码，而这些代码在不提供此功能的实现上无法运行。

典型的 Python 允许 1000 层递归的实现，这对于非递归编写的代码，以及典型的解析树而进行递归的代码来说，已经是足够的了，但对于在大列表上进行递归的来说则不够。


第三，我不相信递归是所有编程的基础。

这是某些计算机科学家，尤其是那些喜欢 Scheme 并喜欢以 "cons" 单元和递归作为编程教学起点的人的基本信仰。

但对我来说，将递归视为所有其他事物的基础只是对基础数学的一种理论上的美好处理方式（Turtles_all_the_way_down），而非日常工具。

出于实际目的，Python 风格的列表（它们是灵活的数组，而不是链表），以及一般的序列，比递归更有用，更适合开始探索编程的奇妙世界。对于经验丰富的 Python 程序员来说，它们也是一些重要的工具。

使用链表来表示一系列的值在大多数情况下都是效率低下的，这明显不符合 Python 的风格。

Python 的大部分库都是以序列和迭代器（当然，还有字典）作为基本构建块编写的，而非链表！

因此，如果你不使用列表或序列，你就会无法使用大量的内置功能。

小甲鱼： 链表是一个递归的数据结构，链表被定义为一个节点（包含数据和一个指向链表的指针），这个指向的链表其实就是链表的剩余部分，这种自我引用的特性是递归的核心。


最后，让我们看看如何实现尾递归优化。

第一个观察是，你不能在编译时做到这一点。我至少看到过一篇博客文章，它使用字节码 hack 在一个 RETURN 操作码前，立即替换一个 CALL 操作码，以跳转到函数体的顶部。

这可能是一个很好的演示，但不幸的是，Python 的编译器无法可靠地确定任何特定的调用是否实际引用了当前的函数，即使它看起来有相同的名字。

参考一下这个：

1. def f(x):
   
2.      if x > 0:
   
3.             return f(x-1)
   
4.     return 0

复制代码

看起来你可以用如下的内容替换函数体：

1. if x > 0:
   
2.     x = x-1
   
3.     <jump to top>
   
4. return 0

复制代码

这看似简单，但是现在加入下面这个：

1. g = f
   
2. def f(x):
   
3.       return x
   
4. g(5)

复制代码

调用 g(5) 会调用前面的 f，但是 “递归” 调用不再递归！

在运行时，'f' 的名字被重新绑定到后面的非递归定义，所以返回的值是 4，而不是 0。

虽然我同意这个特殊的例子的风格很糟糕，但这是 Python 语义的一个定义良好的部分，有很多合理的用途，

一个希望 f 的定义将保持不变的编译器如果做了这样的替换，可能会在实际的代码中引入足够多的错误，甚至引发公愤。


另一篇博客文章展示了可以用来实现尾递归的装饰器，这些装饰器使用神奇的异常或返回值。

这些可以用普通的 Python 编写（尽管那篇文章展示了一个优化的 Cython 版本，声称它只慢 10%，虽然它似乎并不是线程安全的）。

如果这个触动了你的神经我不会试图阻止你，但我会强烈反对将这样的东西包含在核心发行版中：

使用这样的装饰器有很多注意事项，因为它必须假设任何递归调用（在装饰的函数中）都是尾递归的，可以被消除。

否则，在经验较少的用户手中，这可能很容易导致灾难。

例如，公认的阶乘的递归定义并不是尾递归的：

1. def fact(n):
   
2.       if n > 1:
   
3.             return n * fact(n-1)
   
4.       return 1

复制代码

还有很多函数包含一个尾递归调用和另一个非尾递归的递归调用；装饰器不能处理这样的情况。

另一个装饰器不能处理的微妙之处是在 try 块内的尾递归调用：这可能看起来可以被消除，但不能，因为 TRE 可能会移除由语言保证的异常处理。

由于所有这些原因，我认为装饰器方法是注定要失败的，至少对于一般的用户来说。


然而，如果有人决心将 TRE 添加到 CPython 中，他们可以大致按照以下方式修改编译器。

首先，确定 “安全” 的尾递归调用位置。这可能是一个 CALL 操作码紧接着一个 RETURN 操作码，并完全在任何 try 块之外（注意：我忽略了不同的 CALL_* 操作码，应该可以使用相同的方法来处理它们）。

接下来，将每一个这样的 CALL-RETURN 操作码对替换为一个单独的 CALL_RETURN 操作码。

编译器不需要尝试检查被调用的函数的名称是否与当前的函数相同：新的操作码可以仅通过节省解码第二个操作码的时间来表示所有 CALL+RETURN 组合的节省。

如果在运行时确定这个特定的调用不适用于 TRE，那么将执行 CALL 后跟 RETURN 操作码的常规操作（我猜你可以添加一种由调用位置索引的缓存机制来加速运行时的决定）。


在确定是否可以应用 TRE 时，你可以应用几个级别的激进程度。

最不激进的 “纯粹” 方法将只在被调用的对象是当前堆栈帧中已经运行的函数时优化调用。

此时我们只需要清除当前堆栈帧中的局部变量（以及其他隐藏的状态，如活动的循环），从评估堆栈设置参数，然后跳转到顶部。

（微妙之处：新的参数，通过定义，在当前的堆栈帧中出现。这可能只是复制它们的问题。关键字参数、可变长度的参数列表和默认参数值都会带来更多的微妙之处……不过这都只是编程的简单问题）


更激进的版本还将识别出方法是尾递归的情况（即被调用的对象是一个绑定方法，其底层函数与当前堆栈帧中的函数相同）。

这只需要更多的编程即可实现；CPython 解释器代码（ceval.c）已经有了对方法调用的优化。（我不知道这会有多大的用处：我预计喜欢使用函数式编程风格的程序员可能会喜欢尾递归风格，并可能不会使用类和对象。:-)


理论上，你甚至可以优化所有被调用的对象是 Python 编写的函数或方法的情况，只要当前堆栈帧对象可以容纳新调用所需的局部变量的数量。

（CPython 中的 Frame 对象在堆上分配，并基于局部所需的空间有变量分配大小；已经有重用 frame 对象的机制）

这将优化那些相互尾递归的函数，但是，它也会在大多数情况下禁用堆栈追踪，所以这可能不是一个好主意。


一个更温和的变体是创建 Python 级的堆栈帧对象就像以前一样，但复用 C 堆栈帧。

这将创建一个类似于无堆栈 Python 的近似，尽管通过递归一个内置函数或方法仍然很容易耗尽 C 堆栈。


当然，所有这一切都无法解决我前三个观点。

将你的递归函数重写为循环实现真的会很难吗？

（毕竟，TRE 只解决了可以轻松用循环替换的递归。:-)

yinda_peng

算法图解中对于尾递归只是提了一句，想必是因为用Python描述的原因