一起动脑筋 · 先看一个小故事
要给 4 个盒子贴标签，机器人先贴一个，剩下 3 个仍用同一办法。怎样判断这是合适的拆法？
把过程摊开来看
- 原任务处理 4 个
- 做一小步处理 1 个
- 剩余任务处理 3 个
- 最小任务0 个就结束
适合递归的拆分要保留相同的问题形式，同时让规模变小。
“做一小步”和“处理剩余部分”合起来，必须正好解决原问题，不能漏掉，也不能重复。
01什么叫“小问题里的小问题”？
有些问题可以自然地说成：
“如果我已经会解决更小的同类问题，那么当前问题只需要再做一点工作。”
这正是递归最适合的结构。
02设计递归第一步：先说清函数是什么意思
例如：
int sumTo(int n)先规定它的含义：
返回从 1 到 n 的整数和。
只有函数含义清楚，后面的递归关系才不会乱。
03第二步：找最简单的问题
当 n == 0：
1 到 0 没有数，总和定义为 0
if (n == 0) {
return 0;
}04第三步：把当前问题缩小
如果已经知道 sumTo(n - 1) 能算出前 n-1 个数的和，那么：
sumTo(n) = n + sumTo(n - 1)
return n + sumTo(n - 1);05为什么可以“相信”下一层？
因为函数的定义已经说清楚了：sumTo(k) 的任务就是求 1 到 k 的和。
递归设计时，不需要在当前层重新展开所有更深细节，只要保证：
函数含义明确
每一层做同一种任务。
规模变小
下一层问题更简单。
能够停止
最终到达基本情况。
06什么问题不适合硬套递归？
如果问题没有自然的“小一号同类问题”，强行递归可能让代码更复杂。
例如简单地从 1 输出到 100，用循环通常更直观。
你已经知道了什么
- 递归适合能缩小成同类子问题的任务。
- 设计递归前要先定义清楚函数的职责。
- 然后寻找基本情况和缩小问题的方法。
- “相信更小问题能解决”是递归思维的重要模型。
- 没有自然递归结构的问题，不必强行使用递归。
下一篇：递归为什么能走迷宫？
轮到你来试一试
贴完第一个盒子后，下一层又从第一个开始，会有什么问题？
想好了吗？点开看解释
可能反复处理同一个盒子，剩余任务没有缩小。需要更新位置和剩余数量。