GESP 5级 · 简单递推

📖 什么是递推？

递推（也叫"迭代"）是一种解决问题的方法：先知道最前面几个答案，然后利用已知答案推导出下一个答案，像多米诺骨牌一样一个接一个地倒下。

生活类比：你知道第1天有1块钱，每天翻倍，问第10天有多少钱？你不需要知道第10天直接是多少，只需要从第1天开始，一天天往后推：

            第1天：1

            第2天：1 × 2 = 2

            第3天：2 × 2 = 4

            第4天：4 × 2 = 8

            ...

            第10天：2⁹ = 512

递推的核心就是：找到递推关系（公式），加上初始条件（起点），就能推出所有答案。

🌟 为什么重要？

解决复杂问题：很多看起来很复杂的问题（数列、路径计数、动态规划），都可以用递推来解决。
动态规划的基础：递推是学习动态规划（DP）的前置技能，DP 本质上就是"带优化的递推"。
竞赛高频：斐波那契、爬楼梯、铺瓷砖、走格子等问题，几乎每次竞赛都会出现。
思维训练：培养"把大问题分解成小问题"的思维习惯，这是编程的核心能力。

📋 前置知识

✅ 数组的基本操作（定义、赋值、遍历）
✅ for 循环
✅ 基本的数学运算（加法、乘法）
✅ 函数的定义和调用

🔢 例1：斐波那契数列

问题：斐波那契数列定义为：f(1)=1, f(2)=1, f(n)=f(n-1)+f(n-2)（从第3项开始，每项是前两项之和）。

求第 n 项的值。

            f(1) = 1

            f(2) = 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

            f(6) = f(5) + f(4) = 5 + 3 = 8

            ...

            序列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55...

关键：只需要记住"前两个数"，就能推出下一个数。所以不需要数组，只需要两个变量就够了！

💻 斐波那契数列（空间优化版）

#include <iostream>
using namespace std;

// 求斐波那契数列第 n 项
// 递推关系：f(n) = f(n-1) + f(n-2)
// 初始条件：f(1) = 1, f(2) = 1
int fibonacci(int n) {
    // 特殊情况：前两项直接返回
    if (n == 1 || n == 2) return 1;

    // a 代表 f(n-2)，b 代表 f(n-1)
    int a = 1;  // f(1) = 1
    int b = 1;  // f(2) = 1

    // 从第 3 项开始，逐项推导到第 n 项
    for (int i = 3; i <= n; i++) {
        int c = a + b;  // f(i) = f(i-2) + f(i-1)
        a = b;          // a 前移一位，变成 f(i-1)
        b = c;          // b 前移一位，变成 f(i)
    }

    return b;  // b 就是 f(n)
}

int main() {
    for (int i = 1; i <= 10; i++) {
        cout << "f(" << i << ") = " << fibonacci(i) << endl;
    }
    // 输出：
    // f(1) = 1, f(2) = 1, f(3) = 2, f(4) = 3, f(5) = 5
    // f(6) = 8, f(7) = 13, f(8) = 21, f(9) = 34, f(10) = 55
    return 0;
}

🔢 例2：爬楼梯问题

问题：有 n 级台阶，每次可以走 1 阶或 2 阶。问从地面走到第 n 级台阶有几种走法？

分析：

要走到第 n 级，最后一步只有两种可能：
1. 从第 n-1 级走 1 阶上来 → 需要先走到第 n-1 级
2. 从第 n-2 级走 2 阶上来 → 需要先走到第 n-2 级

所以：f(n) = f(n-1) + f(n-2)

初始条件：f(1) = 1（走1步），f(2) = 2（1+1 或 2）

发现了吗？递推关系和斐波那契一样！

💻 爬楼梯

#include <iostream>
using namespace std;

int climb(int n) {
    // 基础情况
    if (n == 1) return 1;  // 只有1级台阶：走1步
    if (n == 2) return 2;  // 2级台阶：1+1 或 2，两种走法

    // 递推：a = f(i-2), b = f(i-1)
    int a = 1;  // f(1) = 1
    int b = 2;  // f(2) = 2

    for (int i = 3; i <= n; i++) {
        int c = a + b;  // f(i) = f(i-2) + f(i-1)
        a = b;
        b = c;
    }

    return b;
}

int main() {
    for (int i = 1; i <= 8; i++) {
        cout << "n=" << i << ": " << climb(i) << " 种走法" << endl;
    }
    // n=1: 1种, n=2: 2种, n=3: 3种, n=4: 5种
    // n=5: 8种, n=6: 13种, n=7: 21种, n=8: 34种
    return 0;
}

🔢 例3：铺瓷砖（面积递推）

问题：用 1×2 的瓷砖铺满 2×n 的棋盘，有几种铺法？

分析：考虑最右边的铺法：
1. 竖着放一块 1×2 的瓷砖 → 左边剩下 2×(n-1) 的区域
2. 横着放两块 1×2 的瓷砖（上下各一块）→ 左边剩下 2×(n-2) 的区域

f(n) = f(n-1) + f(n-2)
初始条件：f(1) = 1, f(2) = 2

和斐波那契又一样！很多递推问题的"骨架"是相同的。

📐 递推的一般步骤

📐 写递推的三步法

第1步：找递推关系
f(n) = 某个关于 f(n-1), f(n-2), ... 的表达式
问自己："要算第 n 个，需要用到前面哪些？"

第2步：确定初始条件
最前面几个值是多少？（也叫"边界条件"）
比如 f(1)=1, f(2)=1

第3步：按顺序推导
用 for 循环从前往后，依次计算每个 f(i)
只需要保留需要的前几项，不需要全部存下来

⚠️ 易错点

🚨 常见错误

递推关系找错：不要凭感觉写公式，要认真分析"要算 f(n) 需要用到哪些前面的项"。画个表推几项，验证公式对不对。
初始条件遗漏：递推是从"已知"推向"未知"。如果初始条件少了（比如只给了 f(1) 但递推需要 f(1) 和 f(2)），后面全部算错。
循环起点错误：如果递推需要前两项，循环应该从 i=3 开始（前两项已知）。不要从 i=1 开始，否则访问了未初始化的变量。
更新顺序错误：a = b; b = c; 不能写成 b = c; a = b;。先更新 a（用旧的 b），再更新 b。如果用一个临时变量 c 就没问题。
整数溢出：斐波那契增长很快，f(46) 就超过 int 范围了。如果 n 较大，要用 long long。
和递归搞混：递推是从前往后推（用循环），递归是从后往前推（用函数调用自身）。递推更高效（不重复计算），但思路有时不如递归直观。

📝 练习建议

💡 怎么练？

先手算几项：拿到递推题，先在纸上手动推 5~10 项，找规律，验证你的递推公式是否正确。
画递推表格：做一个表格，左边是 i，右边是 f(i)，逐行填入。这样很容易发现规律。
从简单题入手：先做斐波那契、爬楼梯，再做铺瓷砖、走格子等变体。
练习空间优化：递推不需要存所有项，练习用 2~3 个变量代替数组。
推荐题目：洛谷 P1002（过河卒）、P1028（数的计算）、LeetCode 70（爬楼梯）、LeetCode 509（斐波那契）。

← 上一个：二分查找 📖 返回主目录下一个：简单贪心 →