CC++ & Algorithm

C++递推思想

中等18
语言版本：C++Python
概述：递推就是像爬楼梯一样，从已知的第一步开始，一步一步推出后面的结果。

一步步推导，递推思维让你轻松解决规律问题

你有没有遇到过这样的问题：想知道从第1级台阶走到第10级台阶，每次可以走1级或2级，一共有多少种不同的走法？如果从头数步子，会非常麻烦。但有一种特别巧妙的方法——递推，它能让你像爬楼梯一样，从已知的第一步开始，一步一步推出后面的结果。递推的核心就是：用已经算好的结果去推导新结果，而不是每次都重新算一遍。

在编程中，递推非常常用。比如计算1+2+3+...+100的和，你可以先算出1+2=3，然后加3得6，加4得10……每次都用上一次的和加上下一个数，这就是递推。下面我们就来详细学习递推思想、递推关系式的推导，以及一个最经典的例子——斐波那契数列。

1. 递推思想：从简单到复杂

递推就像玩闯关游戏：你只有通过上一关，才能解锁下一关。在编程里，我们通常用一个循环，从初始值开始，按照固定的规则一步步计算出后面的结果。

生活例子：存零花钱

小明每天存一次零花钱。第一天存1元，第二天存2元，第三天存3元……问第100天他一共存了多少钱？
你可以这样算：

  • 第1天累计：1元
  • 第2天累计：前1天的累计 + 2 = 1+2=3元
  • 第3天累计：前2天的累计 + 3 = 3+3=6元
  • ……

规律就是：第n天的累计金额 = 第n-1天的累计金额 + 第n天新存的钱。
知道第1天的累计=1，然后用循环重复“加下一个数”的动作，很快就能算出第100天的结果。

代码示例：计算1到n的累加和

下面这个程序用递推思想计算1+2+...+100：

#include <iostream>
using namespace std;

int main() {
    int n = 100;          // 要加到100
    int sum = 0;          // 初始累计和为0
    for (int i = 1; i <= n; i++) {
        sum = sum + i;    // 递推：前i-1项的和加上i
    }
    cout << "1加到" << n << "的结果是：" << sum << endl;
    return 0;
}
  • 初始值：sum = 0（还没加任何数）。
  • 递推规则：每次循环，把当前的 i 加到 sum 上，得到新的 sum。
  • 循环执行：从 i=1 加到 i=100，共100步。

这正是递推思想的体现：只需要知道初始值和递推规则，就能轻松算出很大规模的问题，既简单又高效。

2. 递推关系式的推导：找到规律是关键

递推关系式是递推算法的“心脏”。它用一个数学公式描述当前结果如何从前面的结果得到。要推导递推关系式，需要先观察数据之间的变化规律。

生活例子：小明存钱（翻倍版）

小明第一天存1元，以后每天存的钱是前一天的两倍。问第n天他总共存了多少钱？
我们列出前几天的总钱数：

  • 第1天：1元
  • 第2天：1 + 2 = 3元
  • 第3天：3 + 4 = 7元（第3天新存的钱是前一天2元的2倍，即4元）
  • 第4天：7 + 8 = 15元
  • ……

观察规律：第n天的总钱数 = 第n-1天的总钱数 + 第n天新存的钱。
第n天新存的钱是 2^(n-1)（第1天2^0=1，第2天2^1=2，第3天2^2=4……）。
于是递推关系式可以写成：

  • 设 f(n) 为第n天的总钱数
  • 初始值：f(1) = 1
  • 递推关系：f(n) = f(n-1) + 2^(n-1) （n≥2）

代码实现

在C++中，我们可以用循环实现这个递推式。注意需要包含 <cmath> 库来计算2的幂。

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int n = 5;                       // 假设计算第5天
    double total = 0;                // 总钱数，初始为0
    double today = 0;                // 当天新存的钱
    for (int i = 1; i <= n; i++) {
        today = pow(2, i - 1);       // 第i天新存的钱：2^(i-1)
        total = total + today;       // 递推：总钱数加上今天的新钱
    }
    cout << "第" << n << "天总共存了" << total << "元" << endl;
    return 0;
}

推导递推关系式的关键步骤：

  1. 确定初始值（边界条件）：比如第1天的值。
  2. 找到当前项与前面一项或几项之间的运算规律：可能是加法、乘法、指数等。
  3. 将规律写成包含f(n)和f(n-1)的等式。

就像解谜游戏一样，一旦找到正确答案，程序就能飞快地算出任意一天的总钱数。

3. 经典应用：斐波那契数列

斐波那契数列是递推思想的“代言人”。它最早来自一个有趣的故事：假设一对刚出生的兔子，两个月后每个月生一对新兔子，且兔子不会死，问一年后有多少对兔子？结果就是：

  • 第1个月：1对
  • 第2个月：1对
  • 第3个月：2对
  • 第4个月：3对
  • 第5个月：5对
  • ……

规律是：第n个月的兔子对数 = 第n-1个月的兔子对数 + 第n-2个月的兔子对数。

递推关系式

用数学语言表示：

  • F(1)=1，F(2)=1
  • F(n)=F(n-1)+F(n-2) （n≥3）

这个数列在自然界中也很常见，比如菠萝的鳞片、向日葵的花盘螺旋数等。

用递推循环实现（高效）

如果用递归函数直接计算 F(n)，会重复计算很多次，效率很低。比如计算 F(5) 会计算 F(3) 两次。而用递推循环从第一个数开始，依次算出后面的数，只需循环 n 次。

下面是用数组存储斐波那契数列前20项的代码：

#include <iostream>
using namespace std;

int main() {
    int n = 20;                     // 计算前20项
    long long fib[21];              // 用数组存储，下标从1开始（注意大小至少n+1）
    fib[1] = 1;                     // 第1项
    fib[2] = 1;                     // 第2项
    cout << "斐波那契数列前" << n << "项：" << endl;
    cout << fib[1] << " " << fib[2] << " ";
    for (int i = 3; i <= n; i++) {
        fib[i] = fib[i-1] + fib[i-2];   // 递推关系：前两项之和
        cout << fib[i] << " ";
    }
    cout << endl;
    return 0;
}

运行结果：
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765

利用递推，我们只需循环20次就能得到所有结果，比递归快得多。斐波那契数列不仅在数学中有趣，还在计算机算法、自然界的动植物生长中频繁出现，是理解递推的好帮手。

常见错误与注意事项

1. 忘记初始化或初始值错误

递推必须从一个已知的起点开始。比如累加和的sum要初始化为0，斐波那契数列的fib[1]和fib[2]必须手动赋值。如果忘记初始化，程序会使用随机值，结果完全错误。

2. 数组下标越界

当用数组存储递推结果时，要确保下标从0还是从1开始，以及数组大小足够。例如上面的斐波那契代码，如果写fib[n]而数组只开了n的大小，访问fib[n]就会越界（因为下标从0开始，有效范围是0~n-1）。建议声明为long long fib[n+2];或更大一些。

3. 递推关系写错

递推关系必须反映真实的规律。比如累加和是sum = sum + i，不是sum = sum + i+1；斐波那契是fib[i] = fib[i-1] + fib[i-2]，不是fib[i] = fib[i-1] + fib[i-1]。写之前先在小本子上列几个值验证一下。

4. 混淆递推与递归

递归是函数自己调用自己，容易导致重复计算和栈溢出（比如求斐波那契数列第50项如果用递归会卡死）。而递推是用循环从前往后算，效率高且稳定。新手容易觉得递归写起来简单，但一旦数据规模变大，一定要选用递推。

完整可运行示例：爬楼梯问题

结合递推思想，我们来看一个经典问题：小明爬楼梯，每次可以走1级或2级台阶，求走到第n级台阶有多少种不同的走法。
这和斐波那契数列本质相同：

  • 走1级：只有1种（1步）
  • 走2级：有2种（1+1 或 2）
  • 走3级：可以先走到第1级再走2级，或先走到第2级再走1级，所以 f(3)=f(1)+f(2)=1+2=3
  • 一般地：f(n)=f(n-1)+f(n-2)（n≥3）

下面是一个完整的程序，输入n，输出走法数：

#include <iostream>
using namespace std;

int main() {
    int n;                          // 台阶数
    cout << "请输入台阶数：";
    cin >> n;

    long long ways[100] = {0};      // 用数组存储走法数，假设n不超过100
    ways[1] = 1;                    // 1级台阶：1种走法
    ways[2] = 2;                    // 2级台阶：2种走法

    for (int i = 3; i <= n; i++) {
        ways[i] = ways[i-1] + ways[i-2];   // 递推：走到第i级的方法数
    }

    cout << "走到第" << n << "级台阶共有 " << ways[n] << " 种走法" << endl;
    return 0;
}

你可以试试输入10，看看结果是不是89种？这正是斐波那契数列第10项（从f(1)=1, f(2)=2算起）。

相关指引

掌握了递推思想，你可以进一步学习更高级的算法：

  • 动态规划：递推是动态规划的基础，很多求最优解的问题（比如背包、最长子序列）都用递推关系。
  • 数列求值：等差数列、等比数列、组合数等都可以用递推快速计算。
  • 递归与递推的对比：递归写法简洁但效率低，递推写法稍复杂但速度快，适合大数据。

建议你多找一些生活中的规律问题练习，比如：

  • 每天多存1块钱，30天共存多少？
  • 电影院第一排有10个座位，以后每排多2个，第10排有多少个座位？
  • 用递推画出杨辉三角形（每个数是它上方两个数之和）。

只要肯动脑筋，递推就能成为你编程工具箱里一把锋利的刀！

例题精讲

1单选题

以下关于递推思想的描述，正确的是？

A递推是从未知结果出发，逆向推导已知条件
B递推是利用递归函数调用自身来解决问题
C递推是从已知的初始条件出发，通过重复的递推关系逐步求解后续结果
D递推只能用于数学问题，不能用于编程
2判断题

递推思想中，必须明确初始条件（边界值）才能逐步推导后续结果。

3填空题
以下代码用递推思想计算斐波那契数列的第n项（n≥1）。已知递推关系为f(1)=1, f(2)=1, f(n)=f(n-1)+f(n-2) (n>2)。请补全代码。

int fib(int n) {
    if (n <= 2) return 1;
    int a = 1, b = 1, c;
    for (int i = 3; i <= n; i++) {
        ___;
        a = b;
        b = c;
    }
    return b;
}
4单选题

假设有递推关系：f(1)=2, f(n)=2*f(n-1)+1 (n>=2)。下列哪个选项是f(3)的值？

A5
B7
C11
D15
5填空题
用递推思想解决爬楼梯问题：一次可以迈1阶或2阶，问上到第n阶楼梯有多少种不同的方法。已知递推关系：dp[1]=1, dp[2]=2, dp[n]=dp[n-1]+dp[n-2] (n>2)。请补全以下代码。

int climbStairs(int n) {
    if (n <= 2) return n;
    int dp1 = 1, dp2 = 2, dpn;
    for (int i = 3; i <= n; i++) {
        ___;
        dp1 = dp2;
        dp2 = dpn;
    }
    return dp2;
}