什么是尾递归优化? 如何把递归转化成迭代？

递归的迷思

在计算机科学经典著作，比如SICP中，作者花了大量的笔墨介绍递归。而一些现代编程语言（如Python）则对递归持非常谨慎的态度。在函数式编程中被视为空气一般常见的递归思维，为何在Python社区成了某种禁忌？

到底什么是递归？它有什么问题？有的人非常喜欢，有的人不喜欢它，他们到底在争论什么？我对这种现象感觉很好奇，做了一些研究，在这里整理一下研究结果。本文主要受SICP第一章第二节的启发，我会解释基本概念，介绍Python作者对递归的看法，还会讲在使用不支持尾递归优化的语言的时候，如何把递归写成迭代。

递归的本质

首先我们要说清楚什么是递归，因为它是很多误解产生的根源。容易让人感到困惑的是它在不同的语境下代表的意思是不一样的。

在计算机科学中递归可以用来来指代一种解决问题的方法，它指一种通过重复将问题分解为同类的子问题而解决问题；当我们说一个函数或者一个数据结构是递归的的时候，我们说的是这个数据结构或者函数在内部指向自身或者调用自身；当我们说一个运算过程是递归的时候，我们说的是一个运算中的值取决于另一个运算，因此我们先求出另一个运算的值的过程。

比如一个树形的数据结构，一个节点的内部又指向和与自己内部结构相似的节点，我们认为它是一个递归的结构。本文后面会讲到。

再看递归函数是怎么写的，下面是求阶乘的一个递归函数示例：

def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n - 1)

在上面这个示例中，函数内部调用了自身，因此这是一个递归函数。

让我们来思考一下，假如带入数值5，这个函数求值的过程：

factorial(5)
= 5 * factorial(4)
= 5 * 4 * factorial(3)
= 5 * 4 * 3 * factorial(2)
= 5 * 4 * 3 * 2 * factorial(1)
= 5 * 4 * 3 * 2 * 1
= 5 * 4 * 3 * 2
= 5 * 4 * 6
= 5 * 24
= 120

把5带入程序后首先得到5 * factorial(5 - 1)，我们可以计算出 5 - 1的值4， 但是我们还不知道factorial(4)的值，因此先保留5 *这个操作，具体来说是保存在一个叫做堆栈（Stack，后面简称栈，不要和堆 Heap弄混了）的数据结构中，等得出factorial(4)的值之后再执行运算。可以看到它是一个先递进再回归的过程，这种过程被称为递归过程。

再看一下另外一个递归函数：

def fact_iter(n, acc=1):
    if n == 1:
        return acc
    else:
        return fact_iter(n - 1, n * acc)

它的求值过程：

fact_iter(5)
= fact_iter(5, 1)
= fact_iter(4, 5)
= fact_iter(3, 20)
= fact_iter(2, 60)
= fact_iter(1, 120)
= 120

在上面这个示例中，函数内部同样调用了自身。带入5，实际上是求fact_iter(5, 1)，得到fact_iter(5 - 1, 5 * 1)，首先会求出两个参数的值，再得到fact_iter(4, 5)…… 可以看到这个这并不是一个先扩张后收缩的过程，而是用固定数量的状态变量来存储中间状态，这种过程我们称为线性迭代过程。

是的，你没看错！上面这个函数是一个递归函数，这个递归函数求值的过程却是一个线性迭代过程。需注意这是求值过程的概念模型（也是支持尾递归优化的语言中的实际行为，在Python里，这个函数的每次调用仍然会压栈。

尾递归，尾递归优化

了解完递归，我们再来了解一下尾递归。

首先看一下这个概念的语言描述：尾递归特指函数在尾部位置调用自身的情形（Tail Recursive Call，简称为TRC），是尾调用（Tail Call）的一个子集。而尾调用是指一个函数里的最后一个动作是返回一个函数的调用结果的情形。

我知道你听糊涂了，还是看一个例子：

def foo(data):
    a(data)
    return b(data)

在上面这段代码中，b函数是返回值之前最后调用的函数。b函数所在的位置被称为尾巴。b函数在尾巴的位置被调用，所以它是尾调用。相对地，函数a的调用不在尾巴的位置，就不是尾调用了。

如果在尾巴的位置调用的不是函数b，而是函数foo，那么它是一个特殊尾调用——一个尾调用的递归函数，或者直接称为尾递归。

现在回想一下上面的两个递归函数的例子：在第一个例子中，函数返回的是一个乘法运算 n * factorial(n -1), 所以它不是一个尾调用，自然也就不是尾递归；第二例子却属于尾递归。

我们之前说过，在递归过程中运算和值会先保存在栈里：factorial(5) 挂起了 4 次待完成的乘法，factorial(10000) 就要挂起 9999 个栈帧——内存需求随递归深度线性增长，这就是问题所在。如果把这个递归函数写成尾递归的形式，在计算的过程中，状态会随着参数传递给下一层，运算结果不在需要用到之前的运算状态。编程语言实现时若对递归过程进行优化，使其直接丢弃前序运算而非压栈保存，可显著降低函数的内存需求。

所以，递归函数未必消耗大量资源，前提是编程语言实现了尾递归优化。

尾递归优化听起来很美好，在SICP写作的年代，Scheme是唯一明确要求尾调用优化的语言；如今Lua的语言定义也做了同样的保证，ES6规范甚至也要求了它，虽然几乎没有引擎真正实现。

常常可以看到scheme的使用者，在函数定义子函数，然后调用子函数作为返回值。然而在Python以下写法会导致额外一层栈调用：

def factorial(n):
    def inner_fact_iter(n, acc):
        if n == 1:
            return acc
        else:
            return inner_fact_iter(n - 1, n * acc)
    
    return inner_fact_iter(n, 1)

并且Python的作者吉多·范罗苏姆（Guido van Rossum）在博客中明确表示不会在Python中实现尾递归优化，理由有三：

1. 实现尾递归优化以后，会破坏栈跟踪（Stack Trace）的完整性，增加调试难度。
2. Python的‘最小惊奇原则’要求代码行为可预测——若某解释器实现TCO而另一实现不支持，同一递归代码在不同环境下可能表现迥异，这与Python的‘唯一明确方式’哲学冲突。
3. 单纯个人喜恶问题，作者的原话是：“ I don’t believe in recursion as the basis of all programming”。

所以我们使用Python这个工具的时候，就得适应这个工具的特点，记住典型的Python实现支持1000层的栈调用（可以通过sys.setrecursionlimit设置），达到或者超过它会爆栈。

关于”什么时候用递归、什么时候用循环”，网上的说法五花八门，但大多只给结论、不给判断依据。其实前文的分析已经给出了一个可靠得多的标准：看数据的形状。在之前的博客中我讲到一个观点是一个设计良好的程序应该能反应它所操作的数据的数据结构，而有的数据结构它的定义中就指向自身，它天然就是递归的。最典型的递归数据结构就是各种树了，因此把遍历树的方式写成递归的方式是最直观最清楚的。

吉多·范罗苏姆也在他的博文中提到树的遍历，他认为1000层栈够用了，并且在结尾写道尾递归的形式很容易改写成常规的迭代循环的方式。所以接下来我们就来看看如果把递归函数改成迭代的方式。

从递归到迭代

首先看一个简单的例子，就是前面使用的阶乘的例子。

假如Python支持尾递归优化，那么我们只需要把上文的factorial函数写成fact_iter就可以了。但是Python不支持尾递归优化，所以我们还要进一步修改，把尾递归改成迭代。

仔细观察上面fact_iter函数的求值过程，发现每次调用自身的时候n，和用于保存状态的累加器的值都发生了变化。如果直接用赋值而不是函数调用，得到：

def fact(n, acc=1):
    while n > 1:
        (n, acc) = (n - 1, acc * n)
    return acc

这样就把一个尾递归函数转化成使用迭代的函数了。 再看一个复杂一点的情况，二叉树的遍历：

#首先需要定义一个数据结构。一个二叉树要么是一个空值，要么是一个包含另外两个个节点的节点。
import collections
Node = collections.namedtuple('Node', 'val left right')

#几个例子
tree0 = None  # empty tree
tree1 = Node(5, None, None)
tree2 = Node(7, tree1, None)
tree3 = Node(7, tree1, Node(9, None, None))
tree4 = Node(2, None, tree3)
tree5 = Node(2, Node(1, None, None), tree3)

#使用中序遍历来展开一个树，递归的写法
def flatten_recursive(bst):
    if bst is None:
        return []
    return flatten_recursive(bst.left) + [bst.val] + flatten_recursive(bst.right)


#接下来我们看看迭代版中序遍历，用显式栈替代递归
def flatten_iterative(bst):
    result = []
    stack = []
    current = bst
    
    while current or stack:
        # 深入左子树
        while current:
            stack.append(current)
            current = current.left
        
        # 回溯父节点
        current = stack.pop()
        result.append(current.val)
        
        # 转向右子树
        current = current.right
    
    return result

#最后别忘了测试
assert flatten_recursive(tree5) == [1,2,5,7,9]
assert flatten_iterative(tree5) == [1,2,5,7,9]

可以看到在这个转化过程中，逻辑变得复杂了很多。可能需要想一下才能明白，下面的图解或许会有帮助：

迭代过程模拟（以tree5为例）：

1. 初始: current=2, stack=[]
   • 压入2, 转向左节点1
2. 状态: current=1, stack=[2]
   • 压入1, 转向None
3. 回溯: current=None → 弹出1 → result=[1]
4. 转向: current=1.right=None → 弹出2 → result=[1,2]
5. 转向: current=2.right=7 → 压入7 → 转向左节点5……

后续步骤依此类推：不断深入左子树并压栈，走到头就弹出、记录、转向右子树，直到栈空且没有待处理的节点，最终得到 [1,2,5,7,9]。

对比两次改写，一个关键的区别浮出水面：阶乘的改写只用了两个变量，树遍历的改写却必须自己维护一个栈。为什么？因为阶乘的尾递归版本本来就只有固定数量的状态；而中序遍历天生需要记住”处理完左子树之后，回来还要干什么”，这份记忆无论如何都得有地方放。递归时它藏在调用栈里，改成迭代它就显形为那个显式的 stack。换句话说，改写并没有消除状态，只是把状态从隐式变成了显式——这也解释了为什么这类改写总是”逻辑变复杂了”：复杂性没有增加，只是从语言的运行时搬到了你的代码里。

总结

回顾一下本文的内容：递归是函数调用自身，但递归函数的求值过程未必是递归过程——尾递归形式的函数，其求值过程实际上是线性迭代；尾递归优化能让这类函数以常量的栈空间运行，但Python出于调试和一致性等考虑明确不做这项优化；因此在Python中，简单的尾递归（如阶乘）可以直接改写成循环加状态变量，而天然递归的结构（如树的遍历）改写成迭代时，则需要用显式的栈来模拟调用栈。理解了这层对应关系，你就可以在”表达清晰”和”资源可控”之间自由选择了。