递推法——像推倒多米诺骨牌一样解数学题

你有没有玩过多米诺骨牌？只要把第一张牌推倒，后面一张接一张就会跟着倒下。递推法就是这种思路：从已知的第一步开始，根据固定的规律，一步步算出后面所有的答案。

在编程中，递推法专门用来解决“已知初始值，以及前后项之间的变化规律，求第 n 项的值”这类问题。比如爬楼梯、兔子繁殖、存零花钱、计分统计等，都可以用递推法轻松搞定。它比递归快得多，因为每个结果只算一次，不会重复计算。

递推法的两大核心：初始条件 + 递推关系

要使用递推法，你必须先明确两件事：

初始条件：最开始的那几项是多少。比如第一个台阶有 1 种走法，第二个台阶有 2 种走法。
递推关系：相邻项之间的数学关系。比如爬到第 n 级的方法 = 爬到第 n-1 级的方法 + 爬到第 n-2 级的方法。

有了这两样，就可以像搭积木一样，从第 1 项一直推到第 n 项。

? 经典例子：爬楼梯问题（你已经在原有内容中见过）

题目：小明爬楼梯，每次可以跨 1 级或 2 级台阶。请问爬到第 n 级台阶有多少种不同的方法？

这个问题的递推关系用数学公式写就是：

f(1) = 1 （只有 1 级，只能跨 1 步）
f(2) = 2 （2 级：1+1 或 2，共 2 种）
对于 n ≥ 3：f(n) = f(n-1) + f(n-2)

为什么？因为要到达第 n 级，最后一步可能是从第 n-1 级跨 1 步上来，也可能是从第 n-2 级跨 2 步上来。这两种情况的走法互不重叠，加起来就是总走法。

下面这段代码用 两个变量滚动更新 的方式，只用了 O(1) 的额外空间，非常高效：

#include <iostream>
using namespace std;

int main() {
    int n;
    cout << "输入楼梯级数: ";
    cin >> n;
    if (n <= 2) {
        cout << "方法数: " << n << endl;
        return 0;
    }
    int a = 1, b = 2; // a表示f(1), b表示f(2)
    for (int i = 3; i <= n; i++) {
        int c = a + b; // f(i) = f(i-1) + f(i-2)
        a = b;
        b = c;
    }
    cout << "方法数: " << b << endl;
    return 0;
}

这段代码直接用两个变量 a 和 b 保存前两项，每算出一项就往前滚动一次，最后 b 中存的就是 f(n)。空间省了，速度也快。

? 再加一个生活例子：存零花钱

假设你每天存钱，规则是这样的：

第一天存入 1 元。
从第二天开始，每天存入的钱是前一天的两倍再加上 1 元。

问：第 n 天你一共能存多少钱（累计总额）？注意这里问的是 当天的存款金额，而不是总积蓄。

递推关系：

f(1) = 1
n ≥ 2 时：f(n) = 2 × f(n-1) + 1

例如：第 1 天 1 元，第 2 天 2×1+1=3 元，第 3 天 2×3+1=7 元，第 4 天 2×7+1=15 元……规律出来了，每项都是 2ⁿ - 1。

你可以用同样的滚动变量写法：

#include <iostream>
using namespace std;

int main() {
    int n;
    cout << "你想算第几天的存款？";
    cin >> n;
    if (n == 1) {
        cout << "第1天的存款: 1元" << endl;
        return 0;
    }
    long long prev = 1;      // f(1) = 1，注意用long long防止溢出
    for (int i = 2; i <= n; i++) {
        long long cur = 2 * prev + 1; // f(i) = 2 * f(i-1) + 1
        prev = cur;
    }
    cout << "第" << n << "天的存款: " << prev << "元" << endl;
    return 0;
}

这个例子告诉我们：递推关系不一定是加法，可以是乘法、减法、甚至更复杂的组合。

? 初学者最容易犯的 5 个错误

初始条件搞错
比如爬楼梯问题，有些人以为 f(0)=1（0 级台阶有 1 种走法），但题目通常从 1 级开始，n≤2 时要单独处理。别把“站在地上”当成一种走法。
递推关系写错符号
有时候题目不是 f(n) = f(n-1) + f(n-2)，而是减号、乘号或者涉及多个前项。一定要先手动验证前几项，保证写出的关系符合实际。
循环的起点和终点搞反
比如写了 for (int i = 2; i < n; i++)，少算了一项。建议用纸笔模拟一遍，检查循环结束后变量里的值是不是你要的第 n 项。
忘记考虑 n 很小的情况
如果 n=1 或 n=2，直接输出初始条件，不要让它进入循环，否则可能出现数组越界或变量未定义。
整数溢出
当 n 比较大时（比如 n=50），结果可能超过 int 的范围（约 21 亿）。这时要用 long long（64 位整数）。如果 n 更大，可能还需要高精度运算。

? 完整可运行代码示例（含两种题型）

下面的程序可以让你选择计算 “爬楼梯” 还是 “存零花钱”，并输出结果。注意代码中的中文注释帮助你理解每行的作用。

#include <iostream>
using namespace std;

int main() {
    int choice;
    cout << "请选择计算类型：1 - 爬楼梯，2 - 存零花钱" << endl;
    cout << "输入 1 或 2：";
    cin >> choice;

    int n;
    cout << "请输入项数 n：";
    cin >> n;

    if (choice == 1) {
        // 爬楼梯：f(1)=1, f(2)=2, f(n)=f(n-1)+f(n-2)
        if (n == 1) {
            cout << "爬到第 1 级台阶的方法数：1" << endl;
            return 0;
        }
        if (n == 2) {
            cout << "爬到第 2 级台阶的方法数：2" << endl;
            return 0;
        }
        long long a = 1, b = 2; // a 存储 f(1), b 存储 f(2)
        for (int i = 3; i <= n; i++) {
            long long c = a + b; // 计算 f(i)
            a = b;               // 滚动更新
            b = c;
        }
        cout << "爬到第 " << n << " 级台阶的方法数：" << b << endl;
    }
    else if (choice == 2) {
        // 存零花钱：f(1)=1, f(n)=2*f(n-1)+1
        if (n == 1) {
            cout << "第 1 天的存款：1 元" << endl;
            return 0;
        }
        long long prev = 1; // f(1) = 1
        for (int i = 2; i <= n; i++) {
            long long cur = 2 * prev + 1; // 递推公式
            prev = cur;
        }
        cout << "第 " << n << " 天的存款：" << prev << " 元" << endl;
    }
    else {
        cout << "输入错误，请重新运行程序。" << endl;
    }
    return 0;
}

你可以把这段代码复制到你的编译器里运行，试试输入 n=10 看看结果。手动算一算前几项，验证程序是否正确。

? 学完递推后，可以继续探索什么？

递推 vs 递归：递归是从后往前层层调用，递推是从前往后循环计算。递归代码简洁但慢，递推速度快，适合大量计算。
记忆化搜索：如果你喜欢递归的思路，但又想避免重复计算，可以开一个数组把算过的结果存下来，这就是“递归 + 备忘录”，效果和递推差不多。
动态规划入门：递推是动态规划的基础。当问题有“最优子结构”和“重叠子问题”时，递推关系就变成了状态转移方程。比如背包问题、最短路径，本质上都是递推。
常见递推题型：方格路径（从左上角走到右下角，只能向右或向下，路径数）、错排问题（n 个人不坐自己座位的方法数）、卡特兰数（括号匹配、出栈序列等）。

递推法就像一把钥匙，能打开很多计数和数列的大门。只要找到初始值和变化规律，你就能用循环轻松算出所有答案。多练几道题，你会发现自己越来越会“找规律”了！

递推法——一步步往前推，算出答案