Ray's Blog

Follow me on GitHub

递归的迷思

在计算机科学经典著作，比如巫师书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 *这个操作，具体来说是保存在一个叫做堆栈的数据结构中，等得出factorial(4)的值之后再执行运算。可以看到它是一个先递进再回归的过程，这种过程被称为递归过程。

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

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

它的求值过程：

fac_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_irter(5 - 1, 5 * 1)，首先会求出两个参数的值，再得到fact_iter(4, 5)…… 可以看到这个这并不是一个先扩张后收缩的过程，而是用固定数量的状态变量来存储中间状态，这种过程我们称为线性迭代过程。

是的，你没看错！上面这个函数是一个递归函数，这个递归函数求值的过程却是一个线性迭代过程。

尾递归，尾递归优化

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

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

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

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

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

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

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

我们之前说过，在递归过程中运算和值会先保存在堆栈里，因此这种过程对内存的需求比较大。如果把这个递归函数写成尾递归状态随着参数传递给下一层，根本不在需要堆栈。在实现一门编程语言的时候，如果对这种递归过程进行优化，使其直接丢弃之前的运算，而不压栈，就大大减少了该递归函数对内存的需求。这种优化过程被称为尾递归优化。

所以，递归函数并不一定是消耗大量资源的，只需要编程语言实现尾递归优化。

可问题在于并不是所有的编程语言都实现了尾递归优化，Python就没有。Python的作者吉多·范罗苏姆（Guido van Rossum）在博客中明确表示不会在pythong中实现尾递归优化，理由有三：

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

所以我们使用Python这个工具的时候，就得适应这个工具的特点，记住典型的Python实现支持1000层的堆栈调用，达到或者超过1000层会爆栈。

关于什么时候应该使用递归什么时候使用迭代（循环）网上的一些说法包括：“循环次数不是特别大，处理逻辑及其复杂，如果用循环算法，可能难于理解时，可优先采用递归算法。 处理逻辑简单，则用循环。”还有“一般而言，将递归代码改写为循环代码可以提高效率，但是一旦改写过程中引入了堆操作，那么结果往往是相反的，因为栈内存的操作消耗要小于堆内存的操作消耗。”

对于这些说法可能需要根据自己的具体情况去验证，不过可以确定，在一些情况下用递归的方法让我们的思考变得容易。在之前的博客中我讲到一个观点是一个设计良好的程序应该能反应它所操作的数据的数据结构，而有的数据结构它的定义中就指向自身，它天然就是递归的。最典型的递归数据结构就是各种树了，因此把遍历树的方式写成递归的方式是最直观最清楚的。

吉多·范罗苏姆也在他的博文中提到树的遍历，他认为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……