设计递归
复习
- 栈：后进先出
- 队列与双端队列：先进先出
- 读懂递归：沿调用栈追踪递归的执行
TL;DR
- 设计递归的关键：缩小问题规模，并确保最终收敛
- 相信更小的同类问题已经被解决，只关心怎么组合
- 别在脑子里展开全部调用，先写出递推关系
- 树、图、排序都大量用到递归
正文
会读递归之后，更实际的问题是：怎样从零设计一个递归？这里有一套很好用的思路。
三步走
面对一个问题，可以按这个顺序想：
- 找最小规模：什么情况下问题简单到可以直接回答？这就是基本情况
- 假设更小的问题已解决：不要去想它具体怎么算的，就当它已经返回了正确答案
- 想清楚怎么组合：用“更小问题的答案”，拼出“当前问题的答案”
最后还要确认一件事：每次递归，问题规模确实在变小，否则永远到不了基本情况。
“信仰之跃”
第二步是很多人卡住的地方：怎么能假设它已经解决了呢？这不是循环论证吗？
不是。因为递归的结构是：当前问题依赖一个严格更小的同类问题，而那个更小的问题，最终会落到基本情况上。 只要这个链条一定收敛，假设它就是合理的。这种“相信递归调用会正确返回”的心态，常被形象地叫作“信仰之跃”。别在脑子里把每一层都展开——那只会越想越乱。
一个例子
以“求一个数组所有元素之和”为例：
求和(数组)：
如果数组为空，返回 0
否则，返回 第一个元素 + 求和(剩下的数组)
最小规模是空数组，答案是 0；更小的问题是把第一个元素去掉后的数组；组合方式就是“第一个元素 + 小问题的答案”。干净利落。
递归特别适合那些结构本身就是递归的问题：树的遍历、图的搜索、分治排序……这些后面都会遇到。当然，递归也有代价——每层调用都要占用栈空间。当深度很大时，可能会栈溢出；有些场景改用循环反而更省。能优雅地递归，也要知道什么时候不该硬递归。
思考题 1
设计递归时，为什么要“假设更小的问题已经被解决了”？
思考题 2
什么情况下，递归可能不如循环合适？
小结
知识点
- 设计递归：找基本情况、假设子问题已解、想清组合
- 必须保证每次递归问题规模变小
- “信仰之跃”指相信递归调用会正确返回
- 深度过大或开销敏感时，循环可能更合适
参考资料
- Wikipedia(zh)：递归 (计算机科学)：设计递归解法的思路
- Wikipedia(zh)：分治法：把问题拆分求解的思路
思考题答案（仅供参考）
思考题 1
因为当前问题本来就依赖一个严格更小的同类问题，而后者最终会落到基本情况并返回正确结果。只要规模一定变小、链条必然收敛，假设子问题已解决就是成立的，无需在脑中展开每一层。
思考题 2
当递归深度很大时，每层都要占用调用栈空间，容易栈溢出；或者当递归带来的函数调用开销明显、而问题本身用循环也能清晰表达时，改用循环更省资源也更直接。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪