递归
递归让函数用规模更小的同类问题计算当前结果。写递归前需要给出子问题定义、终止条件和推进方向；调用栈空间也应计入复杂度。
1. 面试核心
先记住这几条，再读正文- 每个递归分支都必须向终止条件推进。
- 总调用次数决定时间，最大同时活动深度决定栈空间。
- 重复计算同一状态时，可以考虑记忆化；深链输入可改为迭代。
2. 子问题与终止条件
对非负整数 n 求最大公约数时，可以利用 gcd(a,b)=gcd(b,a%b)：余数严格小于正除数，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。本例约定 (0,0) 返回 0；若业务不接受这个值，应拒绝该输入。状态推进可证明终止，比仅凭“有 if 返回”更可靠。
3. 调用次数与深度
递归每次处理一个剩余元素时，T(n)=T(n-1)+O(1)，时间与栈空间都是 O(n)。若每次二分后只走一个分支，且每层 O(1)，时间和深度为 O(log n)。
直接递归计算斐波那契数会反复计算相同子问题，总调用数呈指数增长，调用栈深度却只是 O(n)。记忆化减少重复调用，但需要 O(n) 缓存，不应宣称额外空间为 O(1)。
4. 使用边界
递归适合树、分治和组合搜索。Java 不保证尾调用优化，函数最后一步是递归调用也不能据此忽略栈溢出。面对可能达到十万层的链，应使用显式栈或迭代。
自检时从最小合法输入开始手推，再检查每个分支都缩小问题规模。将结果写入共享列表时，必须区分各分支的私有状态与全局结果，避免递归返回后还保留上一个分支的临时修改。
5 · 面试题卡片
先想答案，再翻面题目来自公开面经。点任意一张进入翻卡，可左右切换，看完回到这里。
逐张翻看 1 张 →5.1 有终止条件的递归为什么仍可能无法终止或发生栈溢出？
出现公司：暂无已核验的公开来源（本站自测）
考察重点：终止条件的可达性、问题规模的推进与最坏调用深度。
参考回答
终止条件必须可达。如果递归参数没有向它推进，调用不会停；即使会停，所需深度也可能超过运行时栈容量。应分别证明每次状态推进、估算最坏深度，必要时改为迭代或显式栈。