本讲定位：四级唯一的”算法思想”专题（其余知识块都是语言特性或排序）。递推是 GESP 编程题的常客，也是五级递归、六级动态规划的直接前身——DP 本质就是”带决策的递推”。这一讲学扎实，后面两级都省力。
对应官方大纲：四级知识块 5「递推算法」——递推算法基本思想、递推关系式推导。
前置知识：一维/二维数组、循环、第 01 讲的函数。
代码说明：本讲代码均已用 g++ 11.5（
-std=c++11）编译运行验证，文中标注的输出即实际运行结果。
递推（recurrence）：从已知的初始情况出发，用一个固定的规则，一步步推出后面的结果。
生活中的例子：今天的存款 = 昨天的存款 + 今天存的钱。只要知道第一天有多少（初始条件）和每天存多少（规则），就能推出任意一天的存款。
数学形式：
$$ f(n) = g\big(f(n-1),\, f(n-2),\, \dots\big) $$
即”第 $n$ 项由前面若干项决定”。
| 要素 | 说明 | 斐波那契的例子 |
|---|---|---|
| ① 初始条件（边界） | 最开始的几项，直接给定 | $f(0)=0,\ f(1)=1$ |
| ② 递推关系式 | 后一项如何由前面推出 | $f(n)=f(n-1)+f(n-2)$ |
| ③ 递推方向 | 从小到大（顺推）还是从大到小（逆推） | 顺推，$i$ 从 2 到 $n$ |
📌 教学核心：GESP 编程题里，难的从来不是写循环，而是”推出关系式”。所以本讲的重点是 §3 的推导方法，代码反而是次要的。让学生养成习惯：动手写代码前，先在草稿纸上写出这三行。
f[0] = 初始值1;
f[1] = 初始值2;
for (int i = 2; i <= n; i++)
f[i] = /* 用 f[i-1], f[i-2] ... 表示 */;
cout << f[n];
结构极其固定：初始化 + 一个循环。这也是递推最大的优点——代码短、不易错、效率高。
$$ f(0)=0,\quad f(1)=1,\quad f(n)=f(n-1)+f(n-2)\ (n \ge 2) $$
前几项：$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, \dots$