10 递推算法
正在加载视频播放器…
GESP C++ 四级：递推算法
核心目标：理解递推算法的基本思想，掌握“确定状态 → 找初始值 → 推递推公式 → 循环求解”的四步法，能熟练解决斐波那契、爬楼梯、平面分割、Recamán 数列等经典递推问题。
递推就是“用前面的结果，推出后面的结果”；初始值是起点，递推公式是规则，循环是引擎，三者缺一不可。
一、考纲定位
根据 CCF 官方考纲，四级知识内容明确包含：
掌握递推算法基本思想、递推关系式的推导以及递推问题求解。
递推算法是 GESP 四级 C++ 考试中必考的算法，在 历年的试卷中多次登场。考试中递推相关考点的常见考法包括：
| 考法 | 说明 | 典型题目 |
|---|---|---|
| 递推概念判断 | 判断关于递推的说法的正误 | 选择题 |
| 递推公式推导 | 给定初始条件和规律，写出递推式 | 选择题、编程题 |
| 递推过程模拟 | 手动计算某一步的结果 | 选择题 |
| 递推编程实现 | 用循环实现递推公式求解 | 编程题 |
二、递推的基本概念
1. 什么是递推
递推是一种通过已知值一步步推导出未知值的算法策略，常用于解决“当前状态依赖前一个或前几个状态”的问题。
直观理解：就像搭积木，从最底下的第一块开始，一层一层往上搭，每一层都依赖下面已经搭好的层。递推算法通过逐步求解当前状态和前一个或几个状态之间的关系来解决问题。
2. 递推的三大核心要素
任何递推问题都必须包含三个部分：
| 要素 | 含义 | 类比 |
|---|---|---|
| 初始值 | 递推的起点，必须明确已知 | 没有第一块积木，无法搭房子 |
| 递推公式 | 描述当前状态如何由前面状态推导出来 | 每一层怎么搭的规则 |
| 递推顺序 | 先算小的，再算大的，不能跳着算 | 必须从底往上搭 |
缺少初始值，递推无法启动；缺少递推公式，无法从已知推出未知；递推顺序错误，计算无法正确进行。
3. 递推与递归的区别
| 对比项 | 递推（Iteration） | 递归（Recursion） |
|---|---|---|
| 实现方式 | 循环 | 函数调用自身 |
| 计算顺序 | 自底向上 | 自顶向下 |
| 适合场景 | 数组、动态规划 | 树形结构、DFS 等 |
| 资源消耗 | 更节省空间 | 占用调用栈多 |
递推从最小的初始值出发，一步步向上计算，直到得到目标值；递归从目标值出发，不断向下分解，直到遇到初始值再向上回归。两者解决的是同一类“状态依赖”问题，但方向和资源消耗不同。
三、推导递推关系式的四步法
Step 1：确定状态（State）
用一个变量或数组表示问题的某个子结果。
思考：问题的“第 i 步”或“规模为 i 时”的结果是什么？
int f[100]; // f[i] 表示规模为 i 时的问题答案
Step 2：写出初始条件（Base Case）
找出最简单、已知的初始值，作为递推起点。
思考：当规模最小（i=0, i=1, i=2…）时，答案是什么？
f[1] = 1; // 规模为 1 时的答案
f[2] = 1; // 规模为 2 时的答案
关键规则：如果递推公式中出现了 f[i-1]、f[i-2]、…、f[i-k]，就必须给出 k 个初始值f[1], f[2], …, f[k]。
Step 3：建立递推关系（Transition）
分析当前状态与前面状态的关系，写出状态转移公式。
思考：要得到规模为 i 的结果，可以从哪些更小的规模推导过来？
f[i] = f[i-1] + f[i-2]; // 当前状态由前两个状态推出
Step 4：使用循环进行求解
利用循环结构逐步计算出最终结果。
for (int i = 3; i <= n; i++) {
f[i] = f[i-1] + f[i-2];
}
cout << f[n] << endl;
四、基础递推例题
例题 1：斐波那契数列
问题：定义 F(1)=1，F(2)=1，F(n)=F(n-1)+F(n-2)（n≥3），求 F(n)。
递推分析：
- 状态表示：
f[i]表示第 i 项的值 - 初始值：
f[1] = 1, f[2] = 1 - 递推关系：
f[i] = f[i-1] + f[i-2]
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int f[100] = {0};
f[1] = f[2] = 1;
for (int i = 3; i <= n; i++) {
f[i] = f[i-1] + f[i-2];
}
cout << f[n] << endl;
return 0;
}
例题 2：青蛙跳台阶
问题：一只青蛙每次可以跳 1 级或 2 级台阶，跳上 n 级台阶有多少种跳法？
递推分析：
- 状态表示：
f[i]表示跳上第 i 级的跳法数 - 初始值：
f[0] = 1（跳 0 级也算 1 种方式），f[1] = 1 - 递推关系：跳到第 i 级，要么从 i-1 跳一步来，要么从 i-2 跳两步来，所以
f[i] = f[i-1] + f[i-2]
int f[100] = {0};
f[0] = 1;
f[1] = 1;
for (int i = 2; i <= n; i++) {
f[i] = f[i-1] + f[i-2];
}
cout << f[n] << endl;
爬楼梯问题的数学模型就是斐波那契数列。
例题 3：阶乘的递推计算
问题：计算 n! = 1 × 2 × 3 × … × n。
- 状态表示：
f[i]表示 i! - 初始值：
f[1] = 1 - 递推关系：
f[i] = f[i-1] * i
long long f[25] = {0};
f[1] = 1;
for (int i = 2; i <= n; i++) {
f[i] = f[i-1] * i;
}
cout << f[n] << endl;
五、GESP 四级递推真题精讲
真题 1：平面分割（2024年6月）
题目：10 条直线，最多可以把平面分为多少个区域？（ ）
A. 55 B. 56 C. 54 D. 58
答案：B
递推分析：
从最简单情况开始寻找规律：
- 0 条直线：1 个区域，
a₀ = 1 - 1 条直线：最多分为 2 个区域，比之前多 1 个，
a₁ = a₀ + 1 = 2 - 2 条直线：最多与已有 1 条直线相交，新增 2 个区域，
a₂ = a₁ + 2 = 4 - 3 条直线：最多与已有 2 条直线相交，新增 3 个区域，
a₃ = a₂ + 3 = 7
递推公式：当画第 n 条直线时，它最多与前面 n-1 条直线形成 n-1 个交点，自身被分成 n 段，每段新增一个区域。因此 aₙ = aₙ₋₁ + n。
逐步计算：
a₀ = 1
a₁ = a₀ + 1 = 2
a₂ = a₁ + 2 = 4
a₃ = a₂ + 3 = 7
a₄ = a₃ + 4 = 11
a₅ = a₄ + 5 = 16
a₆ = a₅ + 6 = 22
a₇ = a₆ + 7 = 29
a₈ = a₇ + 8 = 37
a₉ = a₈ + 9 = 46
a₁₀ = a₉ + 10 = 56
代码实现：
int a[105] = {0};
a[0] = 1;
for (int i = 1; i <= n; i++) {
a[i] = a[i-1] + i;
}
cout << a[n] << endl;
真题 2：Recamán 数列（2024年12月）
题目描述：Recamán 数列的递推规则为：a₁ = 1；对于 n > 1，aₙ = aₙ₋₁ - n（如果结果为正且未出现过），否则 aₙ = aₙ₋₁ + n。求第 k 项。
本题主要考查排序和递推思想的应用。
递推分析：
- 状态表示：
a[i]表示第 i 项的值 - 初始值：
a[1] = 1 - 递推关系：需要判断条件，属于带分支的递推
#include <iostream>
using namespace std;
bool used[1000005] = {false};
int a[100005];
int main() {
int k;
cin >> k;
a[1] = 1;
used[1] = true;
for (int i = 2; i <= k; i++) {
int candidate = a[i-1] - i;
if (candidate > 0 && !used[candidate]) {
a[i] = candidate;
} else {
a[i] = a[i-1] + i;
}
used[a[i]] = true;
}
cout << a[k] << endl;
return 0;
}
关键点：Recamán 数列的递推关系不是固定的加减，而是带条件判断的递推——先尝试减，如果结果为正且未出现过就采用，否则改为加。
真题 3：新汉诺塔（2026年9月）
题目描述：汉诺塔问题添加新规则——圆盘只能从 A→B、B→C、C→A 顺时针移动，求将 n 个圆盘从 A 移到 C 的最少步数。
递推分析：
由于只能顺时针移动，移动 1 步与移动 2 步性质不同，需要引入互相依赖的双状态：
f(n)：将 n 个盘顺时针移动 1 根柱子的最少步数g(n)：将 n 个盘顺时针移动 2 根柱子的最少步数
初始状态（n=1）：
- 1 个盘从 A→B：直接移，1 步，
f(1) = 1 - 1 个盘从 A→C：必须经 A→B→C，2 步，
g(1) = 2
状态转移：
f(n)（A→B）：前 n-1 个盘 A→C（顺移 2 步），第 n 个盘 A→B（顺移 1 步），前 n-1 个盘 C→B（顺移 2 步），所以f(n) = g(n-1) + 1 + g(n-1) = 2g(n-1) + 1g(n)（A→C）：前 n-1 个盘 A→C（顺移 2 步），第 n 个盘 A→B（顺移 1 步），前 n-1 个盘 C→A（顺移 2 步），第 n 个盘 B→C（顺移 1 步），前 n-1 个盘 A→C（顺移 2 步），所以g(n) = g(n-1) + 1 + f(n-1) + 1 + g(n-1) = 2g(n-1) + f(n-1) + 2
long long f[25], g[25];
f[1] = 1;
g[1] = 2;
for (int i = 2; i <= n; i++) {
f[i] = 2 * g[i-1] + 1;
g[i] = 2 * g[i-1] + f[i-1] + 2;
}
cout << g[n] << endl; // 从 A 移到 C 是顺移 2 步
核心考点：双状态递推，两个递推公式互相依赖，必须同时维护。
六、递推的常见题型
| 题型 | 特征 | 典型题目 |
|---|---|---|
| 一维递推 | 当前状态只依赖前 1~2 个状态 | 斐波那契、爬楼梯 |
| 带条件递推 | 递推规则中有 if-else 分支 | Recamán 数列 |
| 双状态递推 | 需要维护两个互相依赖的状态 | 新汉诺塔 |
| 增量递推 | 每步增加一个固定或变化的值 | 平面分割 |
| 多维递推 | 状态是二维或更高维 | 杨辉三角、路径计数 |
七、易错点汇总
- 初始值缺失或不足：递推公式中出现
f[i-k]，就必须提供 k 个初始值，否则数组越界或结果错误。 - 递推顺序错误：必须从小规模算到大规模，不能跳着算。
- 数组越界：初始值赋值和循环边界要对应，
f[0]和f[1]不要混淆。 - 混淆递推与递归：递推用循环自底向上，递归用函数调用自顶向下，两者方向相反。
- 递推公式推导错误：一定要从最小规模手动模拟几步，验证规律是否正确。
- 忘记取模：大数递推时结果可能溢出，需要
long long或取模。 - 多状态递推时遗漏状态：双状态递推必须同时更新两个状态，不能只更新一个。
- 条件递推的判断顺序：如 Recamán 数列，必须“先尝试减，不满足再改加”，顺序不能颠倒。
八、速查表
| 需求 | 写法 | 关键注意 |
|---|---|---|
| 递推四步法 | 状态 → 初始值 → 递推公式 → 循环 | 缺一不可 |
| 斐波那契 | f[i] = f[i-1] + f[i-2] |
初始值 f[1]=f[2]=1 |
| 爬楼梯 | 初始值 f[0]=1, f[1]=1 |
|
| 阶乘 | f[i] = f[i-1] * i |
初始值 f[1]=1 |
| 平面分割 | a[i] = a[i-1] + i |
初始值 a[0]=1 |
| 带条件递推 | 先尝试一种，不满足再换另一种 | Recamán 数列 |
| 双状态递推 | 同时维护 f[] 和 g[] |
新汉诺塔 |
| 递推循环 | for (int i = k+1; i <= n; i++) |
k 为初始值个数 |
| 大数处理 | long long 或取模 |
防止溢出 |
九、总结
递推算法是 GESP 四级必考的核心算法。
- 递推的核心是“用前面的结果推出后面的结果”，自底向上逐步求解。
- 三要素：初始值、递推公式、递推顺序，缺一不可。
- 递推公式中出现
f[i-k]，就必须提供 k 个初始值。 - 推导递推公式时，先从最小规模手动模拟几步，找规律。
- 递推用循环实现，从初始值之后开始循环到目标规模。
- 递推与递归的区别：递推自底向上用循环，递归自顶向下用函数调用。
- 平面分割是增量递推的典型：
a[n] = a[n-1] + n。 - Recamán 是带条件递推的典型：先尝试减，不满足再改加。
- 新汉诺塔是双状态递推的典型：两个递推公式互相依赖。
- 多练“斐波那契”“爬楼梯”“平面分割”“Recamán”四类真题，掌握不同递推模型。
复习建议：先从斐波那契和爬楼梯入手，把四步法写熟；再练平面分割，体会“增量递推”的规律；然后攻克 Recamán 和汉诺塔，理解带条件和双状态递推的处理方式。考试中先确定状态表示，再找初始值，然后推导递推公式，最后用循环实现。