递归
递归用同类子问题求解当前问题。本文负责终止、调用成本和记忆化。
1. 面试核心
先记住这几条，再读正文- 终止条件。 递归终止需要每条分支都向可达的终点推进。只写终止条件还不够，还要保证参数或状态不断接近它。卡 · 子问题与终止条件
- 时间与空间。 递归时间取决于全部调用完成的工作，栈空间取决于同时存在的最大调用深度。大量分支与很深的调用链，分别影响这两项成本。
- 记忆化。 记忆化缓存完整状态的结果，消除同一子问题的重复求值。缓存键必须包含影响结果的全部条件。卡 · 记忆化与缓存键
2. 子问题与终止条件
两个非负整数满足 gcd(a,b)=gcd(b,a%b)。b 大于 0 时，余数严格小于 b，所以最终降至 0。
static int gcd(int a, int b) {
if (a < 0 || b < 0) throw new IllegalArgumentException();
if (b == 0) return a;
return gcd(b, a % b);
}
gcd(18,12) 经 (12,6)、(6,0) 返回 6。本例约定 gcd(0,0)=0。终止条件与递减量共同给出终止证明。
3. 调用次数与深度
递推式 T(n)=T(n-1)+O(1) 表示每次减少一项。时间与栈空间都为 O(n)。每次减半且只访问一支时，两者为 O(log n)。
斐波那契的直接递归重复计算同一参数。总调用数指数增长，最大活动深度却只有 O(n)。一次调用结束后，它的栈帧就不再占据活动路径。
4. 记忆化与缓存键
斐波那契只有 n+1 种非负参数。每个参数只计算一次，可把时间降为 O(n)。缓存与递归栈各为 O(n)，大数运算成本另计。
缓存键必须包含影响结果的所有参数。例如网格路径受位置和剩余资源共同影响。只缓存位置会混合不同子问题。
未计算状态应与合法结果区分。若 0 也是答案，可另用 computed 数组记录。记忆化在完成计算后保存结果。有环依赖仍需检测计算中状态，或改用匹配的求解方法。
5. 使用边界
Java JVM 为方法调用保存栈帧。规范未承诺尾递归自动消除栈帧。十万层深链应改为迭代或显式栈。
显式栈仍需保存未完成任务，其空间应计入复杂度。树的分治结果可在子调用返回后合并。共享路径的恢复机制见回溯。
6 · 面试题卡片
本页题目与参考回答
6.1 有终止条件的递归为何仍会不结束或栈溢出？
考察重点：状态推进与栈深度上界。
参考回答
有终止条件仍不够，还要保证每条分支能到达它，且递归深度不超过线程栈容量。
状态循环会导致无限调用；即使调用次数有限，过深的调用链也可能栈溢出。应证明每次调用都在推进，并根据最坏深度选择递归或迭代。
6.2 记忆化为何需要完整缓存键和独立的未计算标记？
考察重点：状态等价与合法零值。
相关内容：记忆化与缓存键。
参考回答
完整键才能确保复用的是同一个子问题。
省掉资源等条件会把不同结果混在一起。未计算标记还要与合法的 0 区分，否则会重复计算或误判。