第6章递归

🎯 本章学习目标

通过本章的学习，你将能够：

理解递归概念：知道什么是递归，掌握递归的两大要素
理解调用栈：清楚递归调用时栈的工作原理，理解栈溢出
编写递归函数：能设计基线条件和递归条件，写出正确的递归函数
掌握经典递归：熟练掌握阶乘、斐波那契、汉诺塔等经典递归问题
理解全排列：掌握回溯法求全排列的思路（选择-递归-撤销）
分析递归复杂度：能用递归树法分析时间和空间复杂度
掌握记忆化搜索：理解重复子问题，能用 memo 数组优化递归
区分递归与迭代：知道两者的区别和各自的优缺点
避免常见错误：能识别并修复无限递归、参数错误等常见问题
读懂递归代码：能快速追踪递归调用过程，分析输出结果

🗺️ 本章知识图谱

递归
├── 基础概念
│   ├── 递归定义（函数调用自身）
│   ├── 两大要素
│   │   ├── 基线条件（Base Case）：递归出口
│   │   └── 递归条件（Recursive Case）：分解子问题
│   └── 调用栈（Call Stack）
│       ├── 栈帧：参数+局部变量+返回地址
│       ├── 压栈：递归调用时层层压入
│       └── 出栈：基线条件后逐层返回
├── 经典递归问题
│   ├── 阶乘（factorial）
│   ├── 斐波那契数列
│   ├── 汉诺塔（Hanoi）
│   │   ├── n-1移辅助 → 移最大盘 → n-1移目标
│   │   └── O(2ⁿ)
│   └── 全排列（回溯法）
│       ├── 选择 → 递归 → 撤销
│       ├── used 数组标记
│       └── path 保存路径
├── 复杂度分析
│   ├── 时间复杂度：递归树节点数
│   ├── 空间复杂度：递归深度（栈深度）
│   └── 栈溢出问题（递归太深）
├── 记忆化搜索（Memoization）
│   ├── 适用：有重复子问题
│   ├── memo 数组/哈希表缓存结果
│   ├── 先查表，算过直接返回
│   └── 斐波那契：从 O(2ⁿ) 优化到 O(n)
├── 递归 vs 迭代
│   ├── 递归：自顶向下，代码简洁
│   ├── 迭代：自底向上，效率高
│   └── 深度大时用迭代防栈溢出
└── 常见错误
    ├── 没有基线条件 → 无限递归
    ├── 基线条件不对 → 结果错误
    ├── 递归不向基线靠近 → 无限递归
    ├── 汉诺塔参数顺序搞混
    └── 回溯忘记恢复状态

📖 引言

递归是"自己调用自己"的编程范式，是理解分治、DFS、树等后续知识的基础。写好递归的关键在于：找准基线条件、相信递归能完成子任务。

一、递归的概念

🔍 什么是递归？

递归 = 函数直接或间接调用自身。

递归把一个大问题拆解成一个或多个规模更小的同类子问题，通过解决子问题来得到原问题的解。

🧱 递归的两大要素

要素	别名	作用
基线条件（Base Case）	递归终止条件	问题规模小到可以直接给出答案，不再递归，
递归条件（Recursive Case）	递推关系	将问题分解为更小的子问题，调用自身

⚠️ 没有基线条件或基线条件永远无法到达 → 无限递归 → 栈溢出（Stack Overflow）💥

📚 调用栈（Call Stack）

每次函数调用时，系统会在栈上为其分配一块内存（栈帧），保存参数、局部变量和返回地址。递归调用层层压栈，直到命中基线条件后才逐层返回、出栈。

factorial(3)
  → 3 * factorial(2)
        → 2 * factorial(1)
              → 1 * factorial(0)
                    → 1  (基线条件，开始返回)
              ← 1 * 1 = 1
        ← 2 * 1 = 2
  ← 3 * 2 = 6

栈空间是有限的

。递归深度过大（如十万层）会导致栈溢出，这是递归最常见的运行时错误。

二、经典递归问题

1️⃣ 阶乘 n!

0! = 1, 1! = 1
n! = n × (n-1)!   (n ≥ 2)

cpp

#include <iostream>
using namespace std;

long long factorial(int n) {
    if (n <= 1) return 1;          // 基线条件
    return n * factorial(n - 1);   // 递归条件
}

int main() {
    cout << factorial(5) << endl;  // 120
    return 0;
}

2️⃣ 斐波那契数列

F(0) = 0, F(1) = 1
F(n) = F(n-1) + F(n-2)  (n ≥ 2)

cpp

// 朴素递归（存在大量重复计算）
int fib(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fib(n - 1) + fib(n - 2);
}

⚠️ 朴素斐波那契递归的时间复杂度为 O(2ⁿ) ，因为存在大量重复子问题（如 fib(5) 会重复计算 fib(2) 多次）。优化方法见"记忆化搜索"部分。

3️⃣ 汉诺塔（Hanoi）

问题：有三根柱子 A、B、C，A 柱上有 n 个从小到大叠放的圆盘。要求把所有圆盘移到 C 柱，规则：

每次只能移动一个圆盘
大盘不能放在小盘上面

递归思路：

把上面 n-1 个圆盘从 A → B（借助 C）
把最大的圆盘从 A → C
把 n-1 个圆盘从 B → C（借助 A）

cpp

#include <iostream>
using namespace std;

// 将 n 个圆盘从 from 移到 to，借助 aux
void hanoi(int n, char from, char to, char aux) {
    if (n == 1) {
        // 基线条件：只剩一个圆盘，直接移动
        cout << from << " -> " << to << endl;
        return;
    }
    hanoi(n - 1, from, aux, to);   // ① 上面 n-1 个：from → aux
    cout << from << " -> " << to << endl;  // ② 移动最大的圆盘
    hanoi(n - 1, aux, to, from);   // ③ n-1 个：aux → to
}

int main() {
    int n;
    cin >> n;
    hanoi(n, 'A', 'C', 'B');
    return 0;
}

复杂度：移动次数 T(n) = 2T(n-1) + 1，T(1)=1 → T(n) = 2ⁿ - 1 ，时间复杂度 O(2ⁿ) 。

4️⃣ 全排列

问题：输出 1~n 的所有排列。

递归思路：依次确定每个位置放哪个数，用 used 数组标记已使用的数字。

cpp

#include <iostream>
#include <vector>
using namespace std;

int n;
vector<int> path;       // 当前排列
vector<bool> used;      // 数字是否已使用

void dfs(int depth) {
    if (depth == n) {               // 基线条件：已选满 n 个数
        for (int i = 0; i < n; i++)
            cout << path[i] << (i == n - 1 ? '\n' : ' ');
        return;
    }
    for (int num = 1; num <= n; num++) {
        if (!used[num]) {
            used[num] = true;       // 标记使用
            path.push_back(num);    // 选择 num
            dfs(depth + 1);         // 递归确定下一个位置
            path.pop_back();        // 回溯
            used[num] = false;      // 恢复标记
        }
    }
}

int main() {
    cin >> n;
    used.assign(n + 1, false);
    dfs(0);
    return 0;
}

💡 全排列是回溯法的经典入门题，"选择 → 递归 → 撤销选择"的回溯模式在 GESP 五级中频繁出现。

三、递归的复杂度分析

⏱ 时间复杂度：递归树法

画出递归调用树，统计所有节点的工作量之和。

问题	递推式	时间复杂度	说明
阶乘	T(n)=T(n-1)+O(1)	O(n)	单链递归
斐波那契（朴素）	T(n)=T(n-1)+T(n-2)+O(1)	O(2ⁿ)	指数级，重复计算多
汉诺塔	T(n)=2T(n-1)+O(1)	O(2ⁿ)	每次分两个子问题
归并排序	T(n)=2T(n/2)+O(n)	O(n log n)	分治，详见第 7 章
记忆化斐波那契	T(n)=T(n-1)+O(1)	O(n)	每个子问题只算一次

💾 空间复杂度

递归的空间复杂度 = 递归深度 × 每层栈帧大小。

阶乘：递归深度 n → O(n)
汉诺塔：递归深度 n → O(n)（虽然时间是 O(2ⁿ)，但空间只有 O(n)！因为同一时刻只有一条递归路径在栈上）
斐波那契（朴素）：递归深度 n → O(n)

🔑 关键理解：递归的空间取决于最大深度，不是节点总数。因为递归是深度优先的，同一时刻栈上只保存一条路径。

四、递归优化：记忆化搜索（Memoization）

🔍 核心思想

把已经算过的结果存起来，下次直接取用，避免重复计算。

记忆化搜索（Memoization）是"自顶向下"的动态规划——用一个数组/哈希表记录每个子问题的解，遇到相同子问题直接返回缓存值。

🧩 斐波那契：从 O(2ⁿ) 到 O(n)

cpp

#include <iostream>
#include <vector>
using namespace std;

vector<long long> memo;  // 记忆化数组

long long fib(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    if (memo[n] != -1) return memo[n];  // 已计算过，直接返回
    // 未计算过，递归计算并存入 memo
    memo[n] = fib(n - 1) + fib(n - 2);
    return memo[n];
}

int main() {
    int n;
    cin >> n;
    memo.assign(n + 1, -1);  // -1 表示未计算
    cout << fib(n) << endl;
    return 0;
}

效果对比：

n	朴素递归	记忆化递归
10	很快	很快
40	明显卡顿	瞬间完成
50	几乎算不出	瞬间完成

📌 识别重复子问题

当递归树中出现相同参数的重复调用时，就适合用记忆化：

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)  ← 重复
│   │   └── fib(1)
│   └── fib(2)      ← 重复！
└── fib(3)          ← 重复！
    ├── fib(2)      ← 重复！
    └── fib(1)

记忆化后每个 fib(k) 只计算一次，时间复杂度从 O(2ⁿ) 降到 O(n)。

🧩 记忆化搜索模板

cpp

// 通用记忆化模板
ReturnType memo[MAXN];  // 初始化为特殊值（-1 或 -INF）

ReturnType dfs(参数) {
    if (基线条件) return 直接结果;
    if (memo[参数] != 特殊值) return memo[参数];  // 命中缓存

    ReturnType result = 0;
    // ... 根据子问题计算 result
    result = /* 合并子问题结果 */;

    memo[参数] = result;  // 存入缓存
    return result;
}

⚠️ 注意：memo 的初始值必须是正常答案不可能出现的值（如 -1），否则无法区分"未计算"和"已计算且结果为该值"。

五、递归与迭代的转换

🔄 为什么要转换？

方式	优点	缺点
递归	代码简洁、思路清晰、贴近数学定义	栈空间开销、深度过大可能溢出、函数调用有开销
迭代	性能好、无栈溢出风险	代码相对复杂、需手动管理状态

🧩 阶乘：递归 → 迭代

cpp

// 递归版
long long factRec(int n) {
    if (n <= 1) return 1;
    return n * factRec(n - 1);
}

// 迭代版
long long factIter(int n) {
    long long result = 1;
    for (int i = 2; i <= n; i++)
        result *= i;
    return result;
}

🧩 斐波那契：递归 → 迭代（递推）

cpp

// 记忆化递归（自顶向下）
long long fibMemo(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    if (memo[n] != -1) return memo[n];
    return memo[n] = fibMemo(n - 1) + fibMemo(n - 2);
}

// 迭代递推（自底向上）
long long fibIter(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    long long a = 0, b = 1;  // a = F(i-2), b = F(i-1)
    for (int i = 2; i <= n; i++) {
        long long c = a + b;  // F(i) = F(i-1) + F(i-2)
        a = b;
        b = c;
    }
    return b;
}

**💡 转换规律：**记忆化递归是"自顶向下"思考，迭代递推是"自底向上"计算。所有递归理论上都可以转为迭代（用显式栈模拟），但并非都值得——以代码清晰为先。

六、递归易错点汇总

#	易错点	正确做法
1	忘记写基线条件 → 无限递归/栈溢出	每个递归函数必须有明确的终止条件
2	递归条件没有缩小问题规模	确保每次递归调用都向基线条件靠近
3	全排列/回溯忘记恢复状态	递归返回后 `pop_back()` 并恢复 `used`
4	朴素斐波那契递归算大数据导致 TLE	用记忆化或迭代递推优化
5	递归深度过大导致栈溢出	改为迭代或增大栈空间（竞赛中）
6	memo 初始值与合法答案冲突	选不可能出现的值做"未计算"标记
7	汉诺塔参数顺序搞混	牢记：第一参起点、第二参终点、第三参辅助

七、📝 实战练习

练习题 1（判断题）

题目： 递归函数只需要有递归条件（自己调用自己），不需要基线条件。（）

🔑 点击查看答案与解析

答案： 错误 ❌

解析： 递归必须同时具备两个要素：

基线条件（Base Case）：问题规模小到可以直接回答，不再递归
递归条件（Recursive Case）：把大问题拆成子问题，调用自身

只有递归条件没有基线条件 → 无限递归 → 栈溢出（Stack Overflow）💥

🍎 生活比喻：基线条件就像"俄罗斯套娃"的最小那个娃娃——不能再拆了，再拆就碎了。

练习题 2（单选题）

题目： 递归调用时，系统用什么数据结构来保存每一层的函数状态？（）

A. 队列
B. 栈
C. 数组
D. 链表

🔑 点击查看答案与解析

答案： B

解析： 系统使用**调用栈（Call Stack）**来管理函数调用。每次函数调用就压入一个栈帧（保存参数、局部变量、返回地址），函数返回就弹出栈帧。

递归是一层一层往里调，最后从最内层一层层返回——这正好是栈的"后进先出"特性。

选 B。

💡 为什么递归太深会栈溢出？因为栈空间是有限的（通常几MB），递归层数太多，栈帧装不下了就溢出了。

练习题 3（程序阅读题）

题目： 阅读以下递归函数，f(5) 的返回值是？（）

cpp

int f(int n) {
    if (n <= 1) return n;
    return f(n - 1) + f(n - 2);
}

A. 3
B. 5
C. 8
D. 13

🔑 点击查看答案与解析

答案： B

解析：

这是斐波那契数列的递归实现：f(0)=0, f(1)=1, f(n)=f(n-1)+f(n-2)

f(0) = 0
f(1) = 1
f(2) = f(1) + f(0) = 1 + 0 = 1
f(3) = f(2) + f(1) = 1 + 1 = 2
f(4) = f(3) + f(2) = 2 + 1 = 3
f(5) = f(4) + f(3) = 3 + 2 = 5

选 B。

⚠️ 注意：朴素递归求斐波那契时间复杂度是 O(2ⁿ)，因为有大量重复计算！n=5 就要算 15 次，n=40 就已经慢得不行了。

练习题 4（单选题）

题目： 汉诺塔问题：将 n 个盘子从 A 柱移到 C 柱，B 柱做辅助。当 n = 3 时，最少需要移动多少次？（）

A. 5
B. 6
C. 7
D. 8

🔑 点击查看答案与解析

答案： C

解析：

汉诺塔的移动次数公式：f(n) = 2ⁿ - 1

n = 3 时：f(3) = 2³ - 1 = 8 - 1 = 7 次

递推验证：

f(1) = 1
f(2) = 2×f(1) + 1 = 3
f(3) = 2×f(2) + 1 = 7

选 C。

🔥 关键思想：先把 n-1 个盘子移到辅助柱（f(n-1)步），再把最大的盘子移到目标柱（1步），最后把 n-1 个盘子从辅助柱移到目标柱（f(n-1)步）。总共 2×f(n-1) + 1 步。

练习题 5（判断题）

题目： 记忆化搜索（Memoization）通过缓存子问题的结果，避免重复计算，从而降低时间复杂度。（）

🔑 点击查看答案与解析

答案： 正确 ✅

解析： 记忆化搜索的核心思想就是"算过的就存起来，下次直接用"。

以斐波那契为例：

朴素递归：O(2ⁿ)，大量重复计算
记忆化递归：O(n)，每个子问题只算一次

🍎 生活比喻：就像做数学题——第一题做完了把答案写在草稿纸上，后面遇到一模一样的题直接抄答案，不用再算一遍。

练习题 6（单选题）

题目： 用回溯法求 {1, 2, 3} 的全排列，共有多少种？（）

A. 3
B. 6
C. 9
D. 27

🔑 点击查看答案与解析

答案： B

解析：

n 个元素的全排列数 = n! = n × (n-1) × ... × 1

3! = 3 × 2 × 1 = 6 种

分别是：123, 132, 213, 231, 312, 321

选 B。

💡 全排列回溯法三步曲：
选择：选一个没用过的元素加入路径
递归：进入下一层，继续选
撤销：递归返回后，把元素从路径中移除，标记为未使用

练习题 7（单选题）

题目： 用朴素递归求斐波那契数列第 n 项的时间复杂度是？（）

A. O(n)
B. O(n²)
C. O(2ⁿ)
D. O(log n)

🔑 点击查看答案与解析

答案： C

解析：

朴素递归斐波那契的递归树是一棵二叉树，每层节点数翻倍，总节点数约为 2ⁿ。

每个节点对应一次函数调用，所以时间复杂度是 O(2ⁿ)。

这也是为什么 n 稍大（如 n=40）就很慢的原因。

选 C。

🔥 优化方法：用记忆化搜索把时间复杂度降到 O(n)——每个 f(k) 只算一次，存起来以后直接用。

练习题 8（编程题）

题目： 请用递归实现一个函数 int sum(int n)，计算 1 + 2 + 3 + ... + n 的和。

要求：

基线条件：n == 1 时返回 1
递归条件：sum(n) = n + sum(n-1)

在主函数中输入 n，输出结果。

🔑 点击查看答案与解析

参考答案：

cpp

#include <iostream>
using namespace std;

int sum(int n) {
    if (n == 1) return 1;          // 基线条件
    return n + sum(n - 1);         // 递归条件
}

int main() {
    int n;
    cin >> n;
    cout << sum(n) << endl;
    return 0;
}

解析：

求和的递归思路：

1+2+...+n = n + (1+2+...+(n-1))
也就是：sum(n) = n + sum(n-1)
基线条件：n=1 时，sum(1) = 1

调用过程（以 n=3 为例）：

sum(3) = 3 + sum(2)
sum(2) = 2 + sum(1)
sum(1) = 1（基线条件，开始返回）
sum(2) = 2 + 1 = 3
sum(3) = 3 + 3 = 6

💡 递归的核心思想：相信你的函数能完成子任务！ 不用关心 sum(n-1) 具体怎么算的，只要知道它能算对就行。这就是"递归信仰"。

八、📊 考点总结表

考点	重要程度	出题形式	易错点
递归两大要素	⭐⭐⭐⭐⭐	选择/判断	忘记基线条件 → 栈溢出
调用栈原理	⭐⭐⭐⭐	选择/程序阅读	栈的后进先出特性
阶乘递归	⭐⭐⭐	程序阅读	基线条件 n=0 或 n=1
斐波那契递归	⭐⭐⭐⭐⭐	程序阅读/复杂度	朴素递归 O(2ⁿ) 很慢
汉诺塔	⭐⭐⭐⭐	选择/程序阅读	参数顺序搞混；移动次数 2ⁿ-1
全排列（回溯）	⭐⭐⭐⭐	编程题/代码填空	忘记恢复 used 和 path
记忆化搜索	⭐⭐⭐⭐	代码填空/选择	memo 初值不能与答案冲突
递归时间复杂度	⭐⭐⭐⭐	选择	用递归树法分析
递归空间复杂度	⭐⭐⭐	选择	等于递归深度（栈深度）
递归 vs 迭代	⭐⭐⭐	选择/判断	深度大时用迭代防溢出

⭐ 必背速记卡

┌─────────────────────────────────────────────┐
│           递归 · 必背速记卡                 │
├─────────────────────────────────────────────┤
│  1. 递归 = 函数自己调用自己                │
│  2. 递归两要素：基线条件 + 递归条件        │
│  3. 没有基线条件 → 无限递归 → 栈溢出       │
│  4. 调用栈：每层调用压栈，返回时出栈       │
│  5. 空间复杂度 = 递归深度（栈的深度）      │
│  6. 阶乘：fact(n) = n × fact(n-1)         │
│  7. 斐波那契：f(n) = f(n-1) + f(n-2)      │
│  8. 朴素斐波那契 O(2ⁿ)，有大量重复计算     │
│  9. 汉诺塔三步：n-1移辅助、移最大、n-1移目标│
│ 10. 汉诺塔移动次数：2ⁿ - 1                 │
│ 11. 全排列回溯：选择 → 递归 → 撤销         │
│ 12. 记忆化搜索：缓存结果，避免重复计算      │
│ 13. 记忆化把斐波那契从 O(2ⁿ) 降到 O(n)     │
│ 14. 递归自顶向下，迭代自底向上             │
│ 15. 写递归的秘诀：相信子问题能算对         │
└─────────────────────────────────────────────┘

第6章 递归 ​

🎯 本章学习目标 ​

🗺️ 本章知识图谱 ​

📖 引言 ​

一、递归的概念 ​

🔍 什么是递归？ ​

🧱 递归的两大要素 ​

📚 调用栈（Call Stack） ​

二、经典递归问题 ​

1️⃣ 阶乘 n! ​

2️⃣ 斐波那契数列 ​

3️⃣ 汉诺塔（Hanoi） ​

4️⃣ 全排列 ​

三、递归的复杂度分析 ​

⏱ 时间复杂度：递归树法 ​

💾 空间复杂度 ​

四、递归优化：记忆化搜索（Memoization） ​

🔍 核心思想 ​

🧩 斐波那契：从 O(2ⁿ) 到 O(n) ​

📌 识别重复子问题 ​

🧩 记忆化搜索模板 ​

五、递归与迭代的转换 ​

🔄 为什么要转换？ ​

🧩 阶乘：递归 → 迭代 ​

🧩 斐波那契：递归 → 迭代（递推） ​

六、递归易错点汇总 ​

七、📝 实战练习 ​

练习题 1（判断题） ​

练习题 2（单选题） ​

练习题 3（程序阅读题） ​

练习题 4（单选题） ​

练习题 5（判断题） ​

练习题 6（单选题） ​

练习题 7（单选题） ​

练习题 8（编程题） ​

八、📊 考点总结表 ​

⭐ 必背速记卡 ​

第6章递归

🎯 本章学习目标

🗺️ 本章知识图谱

📖 引言

一、递归的概念

🔍 什么是递归？

🧱 递归的两大要素

📚 调用栈（Call Stack）

二、经典递归问题

1️⃣ 阶乘 n!

2️⃣ 斐波那契数列

3️⃣ 汉诺塔（Hanoi）

4️⃣ 全排列

三、递归的复杂度分析

⏱ 时间复杂度：递归树法

💾 空间复杂度

四、递归优化：记忆化搜索（Memoization）

🔍 核心思想

🧩 斐波那契：从 O(2ⁿ) 到 O(n)

📌 识别重复子问题

🧩 记忆化搜索模板

五、递归与迭代的转换

🔄 为什么要转换？

🧩 阶乘：递归 → 迭代

🧩 斐波那契：递归 → 迭代（递推）

六、递归易错点汇总

七、📝 实战练习

练习题 1（判断题）

练习题 2（单选题）

练习题 3（程序阅读题）

练习题 4（单选题）

练习题 5（判断题）

练习题 6（单选题）

练习题 7（单选题）

练习题 8（编程题）

八、📊 考点总结表

⭐ 必背速记卡