考纲要求
- 理解递推是由已知的初始条件出发，按固定规律逐步推出后一项。
- 能用一维数组保存中间结果，实现斐波那契数列这类数列递推。
- 能识别递推关系中的边界条件，避免初值错误导致全部结果偏移。
- 能判断哪些递推可以只用几个变量滚动计算，减少空间占用。
典型题型
- 给出递推关系与初值，要求写出第 n 项。
- 用递推解决上台阶、路径计数等问题。
- 判断递推与递归的区别。
常见错误
- 初值写错，后续每一项都跟着错。
- 递推方向反了，用后一项去求前一项。
- 数组开得太小，第 n 项越界。
- 忘记取模或处理大数溢出。
深入理解
递推只有两个要素
递推 = 初始项 + 转移关系。初始项是已知的前几项，转移关系是用前面的项算出后面的项。斐波那契数列是最标准的例子：初始项 f[1] = 1, f[2] = 1，转移关系 f[n] = f[n-1] + f[n-2]。
long long f[100];
f[1] = f[2] = 1;
for (int i = 3; i <= n; i++) f[i] = f[i-1] + f[i-2];写递推题先问两句：前几项是多少？第 n 项由前面哪几项决定？两句都答对，代码几乎是照抄。答错任何一句，整道题的答案都会偏。
用数组记录，避免重复计算
直接按定义写递归求斐波那契，第 40 项就要算上亿次，因为同一个 f[k] 被反复计算。递推用数组从小到大算一遍，每个值只算一次，f[40] 瞬间得到。
这就是「记忆化」的朴素形式。判断该用递推还是递归的经验是：状态只依赖前面少量几项、且从前往后推得动，就用递推。递推不会爆栈，也不会重复计算，是竞赛里更稳的写法。
初值与溢出
两个常见错误：一是初值写错，例如把 f[1] = f[2] = 1 写成只初始化 f[1]，后面全变成 0；二是溢出，斐波那契到第 47 项就超过 int 的范围，必须用 long long，再大还需要高精度。
题目若只要求第 n 项而不需要历史值，可以用两个变量滚动更新，省掉数组：a = b; b = c; c = a + b;。但要注意更新的顺序，写反了会把中间值覆盖掉。
自编例题
用滚动变量求斐波那契数列
求斐波那契数列第 n 项，已知第 1 项和第 2 项都是 1，从第 3 项起每项等于前两项之和。
long long a = 1, b = 1;
for (int i = 3; i <= n; i++) {
long long c = a + b;
a = b; b = c;
}
cout << (n <= 2 ? 1 : b) << endl;递推只需要前两项就能算出当前项，因此不必保存整个数列。循环里用 a 和 b 分别保存第 i 减 2 项和第 i 减 1 项，算出第 i 项后整体向前滚动。n 较小时直接输出 1，避免循环不执行时结果仍取初始值的情况。递推的时间复杂度是 O(n)，空间复杂度是 O(1)。当结果增长很快时要改用 long long 或按题目要求取模。
相关真题
这块内容在整条路线里的位置：GESP C++ 4 级备考路径。
READY TO START
开始练习
先做一套本级别测评，报告会指出哪些知识点需要重点补；再回到本页对照考纲要求逐条核对，把不确定的条目记下来集中练。
常见问题
递推和递归有什么区别？
递推从初始项正向推到目标项，用循环实现；递归把问题分解成更小的同类问题，用函数调用自身实现，可能有重复计算。
递推结果太大怎么办？
按题目要求取模，或者在每一步计算后都取模。若题目不要求取模，应使用 long long 甚至高精度方法。
递推一定要用数组吗？
不一定。如果每项只依赖最近几项，用几个变量滚动即可；需要回看更早的项或输出中间结果时才用数组。