读懂递归

复习

• 双向链表与循环链表（进阶）：双向链表每个节点还保存指向前一个的指针
• 栈：后进先出
• 队列与双端队列：先进先出

TL;DR

• 递归就是函数调用自己来解决问题
• 递归必须有基本情况，否则会无限递归
• 每次调用都压入调用栈，返回时逐层弹出
• 读懂递归，就是沿着调用栈去追踪

正文

　　前面讲栈时提到，函数调用是靠“调用栈”来保存信息的。有意思的是，当函数调用自己时，这套机制依然成立。这种自己调用自己的写法，就是递归（recursion）。

函数调用自己

　　先看一个最简单的例子——计算阶乘：n! = n × (n-1) × … × 1。

　　用递归可以这样写：

阶乘(n)：
    如果 n 是 0 或 1，返回 1
    否则，返回 n × 阶乘(n - 1)

　　注意这里有两个部分，缺一不可：

• 基本情况（base case）：n 是 0 或 1 时直接返回 1，不再递归
• 递归情况：把问题变成“更小的同类问题”，再乘上 n

没有出口，就会一直走下去

　　基本情况为什么必须有？因为它就是递归的“出口”。

　　如果没有它，函数就会不停地调用自己：阶乘(n) 调 阶乘(n-1)，再调 阶乘(n-2)……永远停不下来，直到把调用栈堆满，程序崩溃——这就是栈溢出（stack overflow）。递归一定要能收敛到某个不再递归的点。

用栈的视角看递归

　　递归到底是怎么执行的？把它和调用栈联系起来就很清楚了。

　　以 阶乘(4) 为例：

1. 阶乘(4) 需要 阶乘(3)，于是先把 4 压栈，去算 阶乘(3)
2. 阶乘(3) 又需要 阶乘(2)，再压栈……
3. 一直到 阶乘(1)，命中基本情况，返回 1
4. 然后开始逐层弹出：阶乘(2) = 2 × 1，阶乘(3) = 3 × 2……最终得到 阶乘(4) = 24

　　所以，递归并没有什么魔法。它只是把“先挂起、等更小的结果、再回来继续算”这个过程，交给了调用栈。看懂了栈，就看懂了递归的执行过程。

　　那么，怎样主动设计出一个正确的递归？下一章来谈。

思考题 1

　　为什么递归必须有“基本情况”？

思考题 2

　　递归调用和调用栈之间是什么关系？

小结

知识点

• 递归是函数调用自身来解决问题
• 必须有基本情况作为出口
• 缺少出口会导致无限递归与栈溢出
• 递归的执行过程可借助调用栈理解

参考资料

1. Wikipedia(zh)：递归：函数调用自身的编程方法
2. Wikipedia(zh)：调用栈：保存函数调用信息的结构

思考题答案（仅供参考）

思考题 1

　　因为它是递归的终止条件。没有它，问题会一直缩小却永不停止，函数不断调用自己，最终耗尽调用栈导致栈溢出。有了基本情况，递归才能在有限步内收敛并返回。

思考题 2

　　递归调用本身就借助调用栈来实现：每深入一层调用，相关信息就被压入栈；命中基本情况后，再逐层弹出并完成计算。因此调用栈正是理解递归执行过程的钥匙。

协议

　　本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

封面图

设计师 | 南国微雪