8 递归应用
GESP C++ 五级：递归应用
核心目标：理解递归的基本原理与三要素，掌握调用栈模型与执行流程，能熟练分析递归算法的时间与空间复杂度，掌握记忆化和尾递归两种优化策略，能解决斐波那契、汉诺塔、辗转相除、字符串反转等经典递归问题。
递归就是“函数调用自己，把大问题拆成小问题”；三要素缺一不可——终止条件、递归式、返回合并；写递归先想“什么时候停”和“怎么变小”；递归优雅但可能低效，记忆化和尾递归是两大优化武器。
一、考纲定位
根据CCF官方考纲，五级知识内容明确要求：
掌握递归算法的基本原理，能够应用递归解决问题，能够分析递归算法的时间复杂度和空间复杂度，了解递归的优化策略。
考核目标进一步指出：“掌握算法复杂度估算方法（含多项式、对数），熟悉二分法、分治法、贪心算法和递归算法的算法思想，能够根据实际情况选择合适的算法并完成相应的问题。”
在GESP五级中，递归是高频考点，常以选择题、程序阅读题和代码填空题的形式出现。递归的核心考法包括：
| 考法 | 说明 | 典型真题 |
|---|---|---|
| 递归函数返回值 | 给定递归函数，手动推导返回值 | fun(20,12)、fun(7) |
| 递归输出序列 | 给定带输出的递归函数，写出屏幕输出 | fun(4)输出序列 |
| 递归与迭代比较 | 比较递归和循环的效率、实现方式 | fiboA vs fiboB |
| 递归复杂度分析 | 分析递归算法的时间/空间复杂度 | 斐波那契O(2ⁿ) |
| 递归优化 | 记忆化、尾递归的识别与效果 | 斐波那契记忆化 |
| 经典递归问题 | 汉诺塔、字符串反转、阶乘 | 汉诺塔代码填空 |
二、递归的基本概念
2.1 什么是递归
递归是指函数在自己的定义中调用自己，每次调用都把原问题缩小一点，直到命中可以直接回答的最小情形。直观理解就像“俄罗斯套娃”——最外层看似复杂，但逐层拆开直至最内核。
2.2 递归 vs 迭代
| 对比项 | 递归 | 迭代（循环） |
|---|---|---|
| 实现方式 | 函数调用自身 | for/while 循环 |
| 计算方向 | 自顶向下分解 | 自底向上累积 |
| 调用栈 | 每层调用分配栈帧 | 无额外栈开销 |
| 时间开销 | 函数调用开销大 | 开销小 |
| 空间开销 | O(递归深度) | O(1)（通常） |
| 适用场景 | 树形结构、分治、回溯 | 线性重复计算 |
| 代码风格 | 简洁、接近数学定义 | 直观、易于优化 |
关键结论：递归代码量短、思路清晰，但因涉及多次函数调用（压栈、跳转、返回），其时间开销与空间开销通常均大于简单的迭代循环。理论上，任何递归程序都可以使用循环改写。
三、递归三要素（写递归的黄金框架）
写递归必须包含三部分，缺了任何一环，要么无法结束，要么结果错误：
| 要素 | 作用 | 典型错误 | 示例 |
|---|---|---|---|
| ① 终止条件（Base Case） | 保证调用链有限，给最小实例直接答案 | 忘写或写错 → 无限栈溢出 | if (n == 0) return 1; |
| ② 递归式（Induction Step） | 将当前问题拆成更小同类问题 | 因子不减小 → 死循环 | return n * fac(n-1); |
| ③ 返回并合并（Combine） | 把子结果拼成父结果 | 漏写加/乘/比较 → 得错值 | 乘法合并结果 |
阶乘示例：
long long fac(int n) {
if (n == 0) return 1; // ① 终止条件
return 1LL * n * fac(n - 1); // ② 递归式 + ③ 返回合并
}
核心原则：先想清楚“什么时候停”和“每次怎么变小”，再写代码。
四、调用栈模型与执行流程
4.1 栈帧
每次函数调用，系统会在内存“栈区”开辟一个栈帧，保存局部变量、返回地址、上层链指针等信息。每一次递归调用 = 压栈，返回时 = 弹栈。
4.2 执行流程：以 fac(4) 为例
调用 fac(4)
└── 调用 fac(3)
└── 调用 fac(2)
└── 调用 fac(1)
└── 调用 fac(0)
↙ 返回 1
↙ 1×1 = 1
↙ 2×1 = 2
↙ 3×2 = 6
↙ 4×6 = 24
返回 24
递推过程（向下）：问题规模不断缩小，直到命中终止条件。
回归过程（向上）：逐层返回计算结果，合并为最终答案。
4.3 栈溢出的风险
栈高度等于递归深度。深度过大（通常 ≥ 10⁵ 层）会耗尽栈空间，触发 栈溢出（Stack Overflow），程序崩溃且无法安全恢复。
五、递归复杂度分析
5.1 时间复杂度：看调用次数 × 每次工作量
三步通用分析法：
- 写出递归式：如 T(n) = T(n-1) + O(1)
- 画出递归树：每层有多少个结点，树有多少层
- 累加每层代价：得到总复杂度
| 递归类型 | 递归式 | 时间复杂度 | 典型问题 |
|---|---|---|---|
| 线性递归 | T(n) = T(n-1) + O(1) | O(n) | 阶乘、求和、辗转相除 |
| 二分递归（不重复） | T(n) = 2T(n/2) + O(n) | O(n log n) | 归并排序、快速排序 |
| 双分支重复计算 | T(n) = T(n-1) + T(n-2) + O(1) | O(2ⁿ) | 朴素斐波那契 |
| 二分查找 | T(n) = T(n/2) + O(1) | O(log n) | 二分查找 |
5.2 空间复杂度：看递归深度
空间复杂度 = 最大递归深度 × 每帧空间大小。通常每帧为 O(1)，因此空间复杂度 = O(递归深度)。
- 阶乘：深度 n，空间 O(n)
- 归并排序：深度 log n，栈空间 O(log n)（额外合并数组 O(n)）
- 二叉树DFS：深度 = 树高
5.3 朴素斐波那契的复杂度陷阱
int fiboA(int N) {
if (N == 1 || N == 2) return 1;
return fiboA(N - 1) + fiboA(N - 2);
}
时间复杂度 O(2ⁿ)，存在天文数字般的重复计算。例如计算 fiboA(5) 时，fiboA(3) 会被计算多次。
| n | 朴素递归调用次数 | 迭代调用次数 |
|---|---|---|
| 10 | ≈ 2¹⁰ = 1024 | 10 |
| 30 | ≈ 2³⁰ ≈ 10⁹ | 30 |
| 50 | ≈ 2⁵⁰ ≈ 10¹⁵ | 50 |
六、递归的优化策略
6.1 记忆化（Memoization）
核心思想：用一个数组（或哈希表）缓存已计算过的子问题结果。当同一状态被多次求值时，直接返回缓存值，避免重复计算。
斐波那契记忆化示例：
const int N = 1e5 + 5;
long long dp[N]; // 0表示未计算
long long F(int x) {
if (x < 2) return x;
if (dp[x]) return dp[x]; // 已算过，直接返回
return dp[x] = F(x - 1) + F(x - 2); // 计算并缓存
}
效果：时间复杂度从 O(2ⁿ) 降为 O(n)，空间复杂度 O(n)。
适用条件：子问题存在重叠（同一状态被多次求解），如斐波那契、区间DP、树形DP。
6.2 尾递归（Tail Recursion）
核心思想：递归调用是函数体中的最后一个操作，且返回值直接返回，不进行额外计算。编译器可将其优化为循环（尾调用消除），复用当前栈帧，避免栈增长。
阶乘尾递归示例：
// 尾递归版本
long long fac(int n, long long acc = 1) {
if (n == 0) return acc;
return fac(n - 1, acc * n); // 尾部调用，无额外计算
}
// 等价循环版本
long long fac_it(int n) {
long long acc = 1;
while (n) acc *= n--;
return acc;
}
识别尾递归：递归调用是否是最后一步，且返回值是否直接返回。
6.3 优化策略对比
| 优化策略 | 核心思想 | 适用场景 | 效果 |
|---|---|---|---|
| 记忆化 | 缓存重叠子问题的结果 | 斐波那契、DP | 时间 O(2ⁿ) → O(n) |
| 尾递归 | 编译器优化为循环 | 阶乘、GCD、累加 | 空间 O(n) → O(1) |
| 改写为迭代 | 手动用循环替代递归 | 任何递归 | 消除栈溢出风险 |
七、经典递归问题
7.1 辗转相除法（GCD）
int gcd(int a, int b) {
if (b == 0) return a; // 终止条件
return gcd(b, a % b); // 递归式：问题规模缩小
}
真题示例（2024年9月） ：
int fun(int a, int b) { if (a % b == 0) return b; else return fun(b, a % b); }
fun(20, 12)的返回值为（ ）。
答案：C. 4
解析：fun(20,12) → fun(12,8) → fun(8,4) → 4。
7.2 汉诺塔
问题描述：将 n 个圆盘从 A 柱借助 B 柱移动到 C 柱，大盘不能压小盘。
递归分析：
- 终止条件：n == 1，直接将圆盘从 A 移到 C。
- 递归式：
- 将 n-1 个盘从 A 借助 C 移到 B
- 将第 n 个盘从 A 移到 C
- 将 n-1 个盘从 B 借助 A 移到 C
void Hanoi(char A, char C, char B, int n) {
if (n == 1) {
cout << A << "->" << C << endl; // 终止条件
return;
}
Hanoi(A, B, C, n - 1); // 将n-1个盘从A借助C移到B
cout << A << "->" << C << endl; // 移动第n个盘
Hanoi(B, C, A, n - 1); // 将n-1个盘从B借助A移到C
}
移动次数：T(n) = 2T(n-1) + 1，解得 T(n) = 2ⁿ - 1，时间复杂度 O(2ⁿ)。
7.3 字符串反转
void reverse(string &s, int left, int right) {
if (left >= right) return; // 终止条件
swap(s[left], s[right]);
reverse(s, left + 1, right - 1); // 递归式：向中间收缩
}
7.4 递归求数组最大值
int findMax(int a[], int l, int r) {
if (l == r) return a[l]; // 终止条件：只有一个元素
int mid = (l + r) / 2;
int leftMax = findMax(a, l, mid);
int rightMax = findMax(a, mid + 1, r);
return max(leftMax, rightMax); // 合并子结果
}
复杂度：T(n) = 2T(n/2) + O(1) → O(n)。
八、递归与分治的关系
核心区别：递归是实现手段，分治是问题模式。
| 对比项 | 递归 | 分治 |
|---|---|---|
| 本质 | 一种实现工具/方式 | 一种解决问题的思路 |
| 关系 | 分治通常借助递归实现 | 递归也可以用于非分治问题 |
| 典型 | 阶乘、汉诺塔 | 归并排序、快速排序、最近点对 |
分治递归模板：
int sol(int l, int r) {
if (l == r) return base; // 终止条件
int mid = (l + r) >> 1;
int leftAns = sol(l, mid); // 递归求解左半
int rightAns = sol(mid + 1, r); // 递归求解右半
return merge(leftAns, rightAns); // 合并子答案
}
九、GESP五级递归真题精讲
真题1：递归返回值推导（2024年6月）
int fun(int n) { if (n == 1) return 1; if (n == 2) return 2; return fun(n - 2) - fun(n - 1); }
fun(7)的返回值为（ ）。
A. 0 B. 1 C. 21 D. -11
答案：D
手动递推：
| n | fun(n) |
|---|---|
| 1 | |
| 2 | |
| 3 | fun(1) - fun(2) = 1 - 2 = -1 |
| 4 | fun(2) - fun(3) = 2 - (-1) = 3 |
| 5 | fun(3) - fun(4) = -1 - 3 = -4 |
| 6 | fun(4) - fun(5) = 3 - (-4) = 7 |
| 7 | fun(5) - fun(6) = -4 - 7 = -11 |
真题2：递归输出序列（2024年6月）
int fun(int n) { cout << n << " "; if (n == 1) return 1; if (n == 2) return 2; return fun(n - 2) - fun(n - 1); }
fun(4)的屏幕输出序列为（ ）。
A. 4 3 2 1 B. 1 2 3 4 C. 4 2 3 1 2 D. 4 2 3 2 1
答案：D
调用过程分析：
fun(4) → 输出 4
调用 fun(2) → 输出 2，返回 2
调用 fun(3) → 输出 3
调用 fun(1) → 输出 1，返回 1
调用 fun(2) → 输出 2，返回 2
返回
输出序列：4 2 3 1 2
真题3：递归与迭代比较（2024年9月）
int sumA(int n) { int res=0; for(int i=1;i<=n;i++) res+=i; return res; } int sumB(int n) { if(n==1) return 1; return n + sumB(n-1); }以下说法错误的是（ ）。
A. sumA体现了迭代思想 B. sumB采用递归方式
C. sumB函数比sumA的时间效率更高 D. 两个函数功能相同
答案：C
解析：递归函数因涉及多次函数调用（压栈、跳转、返回），其时间开销与空间开销通常均大于简单的迭代循环。
真题4：斐波那契递归效率（2023年12月）
int fiboA(int N) { if(N==1||N==2) return 1; return fiboA(N-1)+fiboA(N-2); } int fiboB(int N) { int a=1,b=1,c=1; for(int i=3;i<=N;i++){c=a+b;a=b;b=c;} return c; }以下说法错误的是（ ）。
答案： “fiboA 的时间复杂度低于 fiboB”
解析：fiboA 是 O(2ⁿ) 指数级，fiboB 是 O(n)。
真题5：汉诺塔代码填空（2023年9月）
void Hanoi(char A, char C, char B, int n) { if (n == 1) { cout << A << "->" << C << endl; return; } Hanoi(A, B, C, n - 1); cout << A << "->" << C << endl; ______; }横线处应填入：
Hanoi(B, C, A, n-1)
十、易错点汇总
- 忘记终止条件：无限递归导致栈溢出。
- 终止条件写错：边界值错误导致结果偏差。
- 递归因子不缩小：每次调用问题规模必须减小，否则死循环。
- 递归返回值未合并：漏写加/乘/比较操作，结果错误。
- 混淆递归与迭代的效率：递归通常比迭代慢，空间开销更大。
- 朴素斐波那契复杂度误判：是 O(2ⁿ) 指数级，不是 O(n) 或 O(n²)。
- 栈溢出风险：递归深度过大（≥10⁵）时需改用迭代或手动栈。
- 递归输出顺序混淆：先序输出在调用前，后序输出在调用后。
- 尾递归识别错误：递归调用必须是最后一步且返回值直接返回。
- 记忆化数组未初始化：dp 数组需要初始化为0或-1表示未计算。
十一、速查表
| 需求 | 写法 | 关键注意 |
|---|---|---|
| 递归三要素 | 终止条件 + 递归式 + 返回合并 | 缺一不可 |
| 阶乘 | if(n==0) return 1; return n*fac(n-1); |
终止条件 n==0 |
| 斐波那契（朴素） | if(n<=2) return 1; return fib(n-1)+fib(n-2); |
O(2ⁿ)，需优化 |
| 斐波那契（记忆化） | if(dp[x]) return dp[x]; return dp[x]=F(x-1)+F(x-2); |
O(n) |
| GCD | if(b==0) return a; return gcd(b, a%b); |
辗转相除 |
| 汉诺塔 | Hanoi(A,B,C,n-1); 移动; Hanoi(B,C,A,n-1); |
O(2ⁿ) |
| 字符串反转 | if(l>=r) return; swap(s[l],s[r]); reverse(s,l+1,r-1); |
向中间收缩 |
| 尾递归 | 递归调用是最后一步，直接返回 | 可优化为循环 |
| 时间复杂度 | T(n) = 调用次数 × 每次工作量 | 画递归树 |
| 空间复杂度 | O(递归深度) | 深度 = 树高 |
| 栈溢出 | 深度 ≥ 10⁵ 时需注意 | 改写为迭代 |
十二、总结
递归是GESP五级算法模块的核心分水岭。
- 递归就是函数调用自己，把大问题拆成小问题，直到可以直接回答。
- 三要素缺一不可：终止条件、递归式、返回合并。
- 写递归先想“什么时候停”和“每次怎么变小”。
- 递归执行分递推（向下）和回归（向上）两个阶段。
- 递归的空间复杂度 = O(递归深度)，深度过大会栈溢出。
- 朴素斐波那契递归是 O(2ⁿ) 指数级，必须用记忆化优化为 O(n)。
- 尾递归是最后一步调用自身且直接返回，编译器可优化为循环。
- 任何递归程序都可以改写为迭代，但递归代码通常更简洁。
- 递归是分治的实现手段，分治是问题的解决模式。
- 多练“递归返回值推导”“递归输出序列”“递归与迭代比较”“汉诺塔代码填空”四类真题。
复习建议：先把递归三要素和阶乘、GCD 两个基础模板写熟；再重点练习“手动推导递归返回值”和“递归输出序列”两类程序阅读题；然后攻克斐波那契的记忆化优化和汉诺塔递归；最后理解尾递归和递归与迭代的效率差异。考试中先明确递归的终止条件和递归式，再逐步模拟调用过程，最后检查边界和返回值。