← 目录 / 算法文档 · 模块八递推与递归 / 8.2 递归

8.2　递归

函数调用自己——把一个大问题拆成同结构的小问题，直到小到可以直接回答为止。

本页目录

①递归是什么
②递归的两个必要条件
③调用栈图解：f(4) 的执行过程
④调用树：看清所有分支
⑤记忆化：消除重复计算
⑥竞赛常见递归场景
⑦递归的注意事项

① 递归是什么

递归是函数直接或间接地调用自身来解决问题的技术。它把一个大问题分解成若干个结构完全相同、但规模更小的子问题，当子问题小到可以直接回答时（触底），再把答案一层层往上返回。

一个经典的生活类比：要知道自己是第几代人，只需要问父亲"你是第几代"，然后加一就行了。父亲用同样方法问爷爷，爷爷再问曾爷爷……直到找到有族谱记载的那一位（边界）——答案再一路往回传。

用斐波那契数列来看，递归写法和数学定义几乎一模一样：

C++ · 斐波那契：递归写法

        
          1long long fib(int n) {
2    if (n <= 2) return 1;          // 边界：直接回答
3    return fib(n-1) + fib(n-2);   // 拆成子问题
4}
5
6// fib(5) → fib(4)+fib(3) → (fib(3)+fib(2))+(fib(2)+fib(1))
7// → ((fib(2)+fib(1))+1)+(1+1) → ((1+1)+1)+(1+1) → 5

      

② 递归的两个必要条件

缺少任何一个，递归都无法正确运行

✅ 条件一：边界条件（Base Case）

必须有至少一个"小到可以直接回答"的情况，不再继续调用自身。
if (n <= 2) return 1;
缺少边界 → 无限递归 → 栈溢出崩溃。

✅ 条件二：规模收敛（递进条件）

每次递归调用，问题规模必须严格缩小，最终一定能触底到边界。
fib(n-1) + fib(n-2) n 在减小。
若规模不收敛 → 同样无限递归。

③ 调用栈图解：fib(4) 的执行过程

每次函数调用都会在栈上压入一个"帧"，记录当前的参数和返回地址。下图展示 fib(4) 从下探到回升的完整过程：

调用栈：下探阶段（蓝色）→ 触底（绿色）→ 回升阶段（橙色）

调用

fib(4) → fib(3) + fib(2)

调用

fib(3) → fib(2) + fib(1)

调用

fib(2) → ?

触底 ✅

fib(2) → return 1　（n≤2，直接返回）

触底 ✅

fib(1) → return 1　（n≤2，直接返回）

fib(3) = 1 + 1 = 2

触底 ✅

fib(2) → return 1　（另一支）

fib(4) = 2 + 1 = 3

蓝色是向下调用（问题规模缩小），绿色是触底（边界直接返回），橙色是向上回传结果。
整个过程像一个 V 形：先向下探到最深处，再携带答案一路往上返回。

④ 调用树：看清所有分支

fib(4) 展开成一棵树，可以清楚地看到哪些子问题被重复计算了：

fib(2) 在这棵树里被计算了两次。当 n 更大时，重复计算会呈指数级增长。
fib(40) 的调用次数超过 3 亿次——这就是朴素递归慢的原因，下一节用记忆化解决它。

⑤ 记忆化：消除重复计算

解决方案很简单：算过的子问题结果存起来，下次直接查表，不重复算。这叫记忆化（Memoization），也叫"带缓存的递归"。

加上记忆化之后，每个子问题只会被真正计算一次，时间复杂度从 O(2ⁿ) 直降到 O(n)。

C++ · 记忆化递归（斐波那契）

        
          1long long memo[100];    // 记忆表，全局初始化为 0
2
3long long fib(int n) {
4    if (n <= 2) return 1;           // 边界
5    if (memo[n]) return memo[n];    // ✅ 查表：算过就直接返回
6    memo[n] = fib(n-1) + fib(n-2); // 算完存入表中
7    return memo[n];
8}

      

💡

记忆化 = 递归 + 哈希表（或数组）。从效果上看，记忆化递归和递推（自底向上）几乎等价，只是方向相反。实际上，记忆化递归就是"自顶向下的动态规划"——这也是动态规划的另一种实现方式。

⑥ 竞赛常见递归场景

递归在竞赛中不只用于数列计算，以下是最常见的几类：

C++ · 场景一：全排列（枚举所有排列方案）

        
          1int a[8], n;
2bool used[8];
3
4void perm(int depth) {          // depth：当前填到第几位
5    if (depth == n + 1) {         // 边界：n 位都填完了
6        for (int i=1;i<=n;i++) cout<<a[i]<<" ";
7        cout << endl; return;
8    }
9    for (int i = 1; i <= n; i++) {  // 枚举这一位填什么
10        if (used[i]) continue;         // 已用过就跳过
11        a[depth] = i;  used[i] = true;
12        perm(depth + 1);             // 递归填下一位
13        used[i] = false;              // 回溯：撤销选择
14    }
15}

      

C++ · 场景二：二分递归（快速幂）

        
          1// 计算 a^n mod p，O(log n)
2long long qpow(long long a, long long n, long long p) {
3    if (n == 0) return 1;           // 边界：a^0 = 1
4    if (n % 2 == 0)                  // 偶数次幂：(a²)^(n/2)
5        return qpow(a*a%p, n/2, p);
6    return a * qpow(a, n-1, p) % p;  // 奇数次幂：a × a^(n-1)
7}

      

C++ · 场景三：树的遍历

        
          1// 先序遍历（根 → 左子树 → 右子树）
2void preorder(int u) {
3    if (u == 0) return;             // 边界：空节点
4    cout << u << " ";
5    preorder(left[u]);              // 递归左子树
6    preorder(right[u]);             // 递归右子树
7}

      

⑦ 递归的注意事项

问题	原因	解决方法
栈溢出（Stack Overflow）	递归层数太深，系统调用栈空间耗尽	改用递推（迭代），或增大栈空间
重复计算（TLE）	同一子问题被反复求解	加记忆化数组（memo[]）缓存结果
死递归（无限循环）	边界条件写错，或规模没有收敛	检查边界是否覆盖所有终止情况
整数溢出	递归层数深时中间结果超过 int 范围	改用 long long，注意取模时机

📖

本节小结
・递归 = 边界条件 + 规模收敛的自我调用，缺一不可。
・执行过程是 V 形：先向下探到边界，再携带结果一路向上返回。
・朴素递归可能有大量重复计算，加上记忆化（memo 数组）后等价于动态规划。
・竞赛常见场景：全排列/回溯、快速幂、树的遍历、分治。
・递归层数太深会栈溢出，此时改用递推（迭代）是更稳妥的选择。

1	long long fib(int n) {
2	if (n <= 2) return 1; // 边界：直接回答
3	return fib(n-1) + fib(n-2); // 拆成子问题
4	}
5
6	// fib(5) → fib(4)+fib(3) → (fib(3)+fib(2))+(fib(2)+fib(1))
7	// → ((fib(2)+fib(1))+1)+(1+1) → ((1+1)+1)+(1+1) → 5

1	long long memo[100]; // 记忆表，全局初始化为 0
2
3	long long fib(int n) {
4	if (n <= 2) return 1; // 边界
5	if (memo[n]) return memo[n]; // ✅ 查表：算过就直接返回
6	memo[n] = fib(n-1) + fib(n-2); // 算完存入表中
7	return memo[n];
8	}

1	int a[8], n;
2	bool used[8];
3
4	void perm(int depth) { // depth：当前填到第几位
5	if (depth == n + 1) { // 边界：n 位都填完了
6	for (int i=1;i<=n;i++) cout<<a[i]<<" ";
7	cout << endl; return;
8	}
9	for (int i = 1; i <= n; i++) { // 枚举这一位填什么
10	if (used[i]) continue; // 已用过就跳过
11	a[depth] = i; used[i] = true;
12	perm(depth + 1); // 递归填下一位
13	used[i] = false; // 回溯：撤销选择
14	}
15	}

1	// 计算 a^n mod p，O(log n)
2	long long qpow(long long a, long long n, long long p) {
3	if (n == 0) return 1; // 边界：a^0 = 1
4	if (n % 2 == 0) // 偶数次幂：(a²)^(n/2)
5	return qpow(a*a%p, n/2, p);
6	return a * qpow(a, n-1, p) % p; // 奇数次幂：a × a^(n-1)
7	}

1	// 先序遍历（根 → 左子树 → 右子树）
2	void preorder(int u) {
3	if (u == 0) return; // 边界：空节点
4	cout << u << " ";
5	preorder(left[u]); // 递归左子树
6	preorder(right[u]); // 递归右子树
7	}