算法的故事 / 全书目录0 / 30 章已读

第 02 章

栈与递归——为什么计算机必须记住自己从哪里来？

正在加载交互实验…

第一季 · 人类如何驯服数据
第 2 章配图 1
来源
公元前的希腊神话里，克里特岛上有一座迷宫。传说，迷宫里关着可怕的牛头怪弥诺陶洛斯（Minotaur）。年轻的忒修斯（Theseus）进入迷宫，准备杀死怪物。可是，他遇到了一个比怪物更棘手的问题：即使打败怪物，他怎么走出迷宫？迷宫中有无数岔路，而且通道看起来都差不多。幸好，阿里阿德涅（Ariadne）给了他一团线。
第 2 章配图 2
来源
忒修斯把线的一端系在入口，带着线团走进迷宫。沿着留下的线，他便能找到回去的路。这是古希腊神话，不是栈的真实发明史。但它恰好可以帮助我们理解计算机科学中一个非常重要的问题：一个程序进入了很多层任务，怎样才能按照正确的顺序返回？答案，就藏在我们今天的主角里。

第一幕：一摞盘子，改变了计算机世界

假设一家餐厅有一摞盘子。服务员不断把洗好的盘子放在最上面，客人也总是从最上面拿盘子。最后放上去的盘子，最先被取走。
第 2 章配图 3
来源
这就是后进先出：Last In, First Out，简称 LIFO。
它看起来只是一个日常生活中的小细节。但如果把盘子变成数据，就得到了一种非常有用的数据结构：栈（Stack）。栈最重要的操作只有两个：
  • push：把一个元素压到栈顶。
  • pop：从栈顶取出一个元素。
对于合理实现的栈，这两项操作通常都是 O(1)O(1)。

亲自操作一下

你的第一台栈机器2 个元素
B ← TOP
A
试着连续压入三个元素，然后连续弹出三个元素，观察顺序。
你可能会问：这种只能从顶部操作的数据结构，看起来反而限制很多，为什么要发明它？因为在某些场景里，这种限制不是缺点，而是正确性的重要保障。

第二幕：函数调用之后，计算机怎么回家？

现在，神话结束，我们回到真实的计算机。假设你编写了三个 Python 函数：
python
def A():
    print("进入 A")
    B()
    print("离开 A")

def B():
    print("进入 B")
    C()
    print("离开 B")

def C():
    print("进入 C")
    print("离开 C")

A()
你能预测打印顺序吗？程序首先进入 A，然后 A 调用 B，B 又调用 C。可是一个奇怪的问题出现了：当 C 结束的时候，计算机怎么知道该回到 B，而不是直接返回 A？更进一步，它怎么知道 B 应该从哪一行代码继续执行？这就需要一种特殊的记忆。计算机在调用函数时，会保存与调用相关的状态，通常包括返回地址，以及必要的局部状态或上下文。这类信息由运行时使用**调用栈（Call Stack）**管理。
函数调用与返回模拟器
调用栈（栈顶在上）
A()
当前事件

进入 A()

A 开始执行，准备调用 B。
步骤 1 / 6
现在你发现一个重要的规律：最后被调用的函数，必须最先结束并返回，外层函数才有机会继续。这不就是后进先出吗？假如使用普通队列来管理这些嵌套函数调用，先进入的 A 反而会先退出，显然不符合执行逻辑。所以调用栈不仅是工程实现方式，更与嵌套调用的结构天然匹配。

第三幕：1959年，一个真正的历史转折点

第 2 章配图 4
来源
Edsger W. Dijkstra（艾兹赫尔·戴克斯特拉）荷兰计算机科学家。你今后学习图论时，还会遇到以他命名的最短路径算法。但今天，我们要谈的是他在程序语言实现方面的贡献。
1959年，Dijkstra 正在思考一个难题：如何让计算机正确执行可以递归调用的程序？当时，程序员并不总能像今天一样，自然而然地让函数调用自己。假如一个函数只有一块固定的局部变量存储空间，那么函数再次调用自己时，就可能覆盖上一层调用的变量和返回信息。Dijkstra 在1959—1960年参与解决了 ALGOL 60 中递归调用与变量作用域的实现问题。调用栈由此成为支持递归的重要机制之一。[Stackrev7.doc][cs.utexas.edu][heerdebeer.org]这段历史还有一个精彩的联系。还记得上一章发明快速排序的 Tony Hoare 吗？他曾经有了快速排序的思想，却难以用当时掌握的工具把递归部分实现出来。后来，ALGOL 60 对递归的支持帮助他完成了实现。[德克萨斯大学奥斯汀分校计算机科学][Stackrev7.doc]所以我们前两章其实连起来了：栈支撑了递归，而递归帮助快速排序成为了现实。

第四幕：递归——一个不断把任务交给自己的函数

我们用一个非常简单的 Python 函数来理解递归。
python
def countdown(n):
    if n == 0:
        print("发射！")
        return

    print(n)
    countdown(n - 1)

countdown(3)
运行过程是：
countdown(3)打印 3，然后调用 countdown(2)
countdown(2)打印 2，然后调用 countdown(1)
countdown(1)打印 1，然后调用 countdown(0)
countdown(0)打印“发射！”，停止继续递归
这里有两个关键概念：递归条件（Recursive Case）：问题还没有结束，继续调用自己，但把问题变小。终止条件（Base Case）：问题已经小到可以直接解决，不再继续调用自己。如果缺少终止条件，或者递归过程始终无法抵达终止条件，就可能不断增加调用栈深度。Python 通常会在达到递归深度限制时抛出 RecursionError。

第五幕：真正困难的不是进入，而是返回

我们稍微增加一点难度。
python
def mystery(n):
    if n == 0:
        return

    print("进入", n)
    mystery(n - 1)
    print("离开", n)

mystery(3)
这一次，为什么输出会先是 3、2、1，再变成 1、2、3？因为每一层函数在调用下一层之前，都会暂时停下来。最深层返回后，之前暂停的函数才能依次恢复。
递归执行时间线
进入 3
向深处调用
进入 2
向深处调用
进入 1
向深处调用
到达终止条件
开始返回
离开 1
逐层返回
离开 2
逐层返回
离开 3
逐层返回
1 / 7
这就是递归最重要的特点之一：调用时不断深入，返回时逐层恢复。数学上，一个复杂的问题不断转化成规模更小、结构相同的问题；计算机中，调用栈保存尚未完成的工作。

第六幕：如果不允许使用递归，还能解决问题吗？

当然可以。假设要遍历一棵树，我们可以使用递归：
python
def dfs(node):
    if node is None:
        return

    print(node.value)
    dfs(node.left)
    dfs(node.right)
也可以自己维护一个显式栈：
python
def dfs(root):
    if root is None:
        return

    stack = [root]

    while stack:
        node = stack.pop()
        print(node.value)

        if node.right:
            stack.append(node.right)

        if node.left:
            stack.append(node.left)
注意，为什么要先压入右孩子，再压入左孩子？因为栈是后进先出，左孩子后压入，反而会先被处理。于是你会发现：递归可以隐式使用调用栈，而迭代算法可以显式维护一个栈。两种方法并不是完全相反，而是经常能够相互转化。

终章挑战：一个栈能解开怎样的密码？

在继续下一章之前，给你一道推理题。一个空栈依次执行：
text
push(4)
push(7)
pop()
push(2)
push(9)
pop()
pop()
最后栈顶是什么数字？
这一章，你真正需要带走的，不只是 push() 和 pop()。而是这样一种思维：当任务一层套着一层，最后开始的任务必须最先结束时，栈就是一种自然的组织方式。它出现在函数调用、表达式解析、深度优先搜索、撤销操作、括号匹配等许多场景中。下一章我们将认识栈的另一位亲戚：《队列：为什么最先到达的人，应该最先得到服务？》从银行排队到操作系统调度，再到广度优先搜索，我们会看到一种简单的先进先出规则，如何让计算机安排成千上万项工作。