递归

递归是函数调用自身的过程。设计时必须同时给出递归关系（把原问题化为更小同类问题）和终止条件（可直接求解的边界），否则会无限调用并栈溢出。

从数学式到代码

阶乘满足：f(n)=n·f(n-1)，且 f(0)=1。欧几里得算法满足 gcd(a,b)=gcd(b,a mod b)，终止于 b=0。

long long fac(int n) {
    if (n <= 1) return 1;
    return n * fac(n - 1);
}
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

执行过程与复杂度

每次调用都会建立一个栈帧，递归到边界后按相反顺序返回。递归深度为 d 时额外栈空间通常是 O(d)。阶乘时间、空间均 O(n)；欧几里得算法时间 O(log min(a,b))。

书写检查

1. 参数是否严格向终止条件靠近；
2. 每个递归分支是否覆盖；
3. 是否会重复计算子问题；
4. 递归深度是否可能超过栈容量。

当大问题可拆为多个独立子问题并合并答案时，递归自然引出分治。