C++递推经典问题（斐波那契数列）

什么是递推？为什么学它？

在编程中，“递推”是一种从已知出发、一步步推出未知的思考方法。就像你玩多米诺骨牌：推倒第一块，它撞倒第二块，第二块再撞倒第三块……结果整排都会倒下。递推的核心是利用前面已经算好的结果，计算出后面的结果，特别适合解决那些有规律、能一步一步往前推的问题。

生活中还有很多递推的例子，比如：

零花钱存钱：你每周存10元，第一周有10元，第二周就是10+10=20元，第三周20+10=30元……这其实是一个递推：本周总额 = 上周总额 + 10。
排队买冰淇淋：排在第1个的小朋友花了2分钟，第2个小朋友要等前面的人买完再加上自己的2分钟，所以等待时间依次增加。这些都可以用递推公式来描述。

今天我们要学的斐波那契数列，就是递推里最经典、最有意思的例子之一。

故事：兔子生宝宝（回顾）

这个数列来自一个古老的数学问题——兔子生宝宝。让我们再仔细捋一遍：

假设一对小兔子需要一个月才能长大成年，成年后每个月能生一对新的小兔子（一雌一雄），且兔子不会死。一开始（第1个月）我们有1对刚出生的幼兔。问：第 n 个月一共有多少对兔子？

我们一步步推：

第1个月：1对幼兔（还没长大，不能生宝宝）。
第2个月：幼兔长成了成兔，但还没生宝宝，所以还是1对成兔。
第3个月：这对成兔生下了1对幼兔，所以现在有1对成兔 + 1对幼兔 = 2对。
第4个月：原来的成兔又生1对幼兔，同时上个月的幼兔长成了成兔。这时候有：原来的1对成兔 + 新生的1对幼兔 + 上月幼兔变成的1对成兔 = 总共3对。
第5个月：所有成兔（原来那对+上月变成的那对）各生1对幼兔，加上上个月的幼兔长大，总共5对。

你发现规律了吗？
这个月的兔子总数 = 上个月的兔子总数 + 上上个月的兔子总数。

为什么？因为上个月的所有兔子都存活（就是上个月的总数），而只有成兔能生宝宝。成兔的数量恰好等于上上个月的兔子总数（因为上上个月的幼兔到这个月已经成年了）。所以：

这个月总数 = 上个月总数（全部存活） + 上上个月总数（新生的幼兔）

这就是斐波那契数列的由来：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ……

递推公式

用数学公式来表示斐波那契数列（通常用 F(n) 代表第 n 项）：

初始条件：F(1) = 1，F(2) = 1
递推关系：当 n ≥ 3 时，F(n) = F(n-1) + F(n-2)

注意：有些教材把初始值设为 F(0)=0, F(1)=1，但本例我们按兔子问题取 F(1)=1, F(2)=1。

这个递推关系就是“从两个已知值推出下一个值”。你只需要知道前两个数，就能依次算出所有后面的数。

另一个贴近生活的例子：爬楼梯

我们换个例子加深理解：小明爬楼梯，每次可以跨1级或2级台阶。问：爬到第 n 级台阶，有多少种不同的爬法？

第1级：只能跨1级，1种方法。
第2级：可以两次1级，或一次2级，共2种方法。
第3级：可以从第2级跨1级上来，也可以从第1级跨2级上来，所以方法数 = 第2级的方法数 + 第1级的方法数 = 2 + 1 = 3。
第4级：从第3级跨1级，或从第2级跨2级，方法数 = 3 + 2 = 5。

你看，这又是一个斐波那契数列！只不过初始值变成了 F(1)=1, F(2)=2。递推思想一模一样：当前项等于前两项之和。

C++代码实现（带详细解释）

下面我们用C++循环来计算斐波那契数列的第 n 项。代码里我们使用三个变量来“滚动”更新，避免用数组占用太多空间。

#include <iostream>
using namespace std;

int main() {
    int n;                                  // 用户输入，想求第几个月
    cout << "请输入你想知道第几个月的兔子对数（正整数）：";
    cin >> n;

    int a = 1, b = 1;                        // a存第1个月，b存第2个月
    int result;                              // 用于存放最终结果

    if (n == 1 || n == 2) {
        result = 1;                         // 前两个月都是1
    } else {
        // 从第3项开始循环，一直算到第n项
        // 循环次数 = n - 2
        for (int i = 3; i <= n; i++) {
            result = a + b;                 // 当前项 = 前两项之和
            a = b;                          // 把原来的b变成新的a（向前滚动）
            b = result;                     // 把新算出的结果变成新的b
            // 下一轮循环时，a就是原来的b，b就是刚算出的结果
        }
    }

    cout << "第" << n << "个月的兔子对数是：" << result << endl;
    return 0;
}

变量变化追踪（以 n=5 为例）：

循环 i	a (原来)	b (原来)	result = a+b	新的 a	新的 b
初始	1	1	/	1	1
i=3	1	1	2	1	2
i=4	1	2	3	2	3
i=5	2	3	5	3	5

循环结束，result = 5，正确。

运行示例：

请输入你想知道第几个月的兔子对数（正整数）：6
第6个月的兔子对数是：8

新手常见错误

忘记处理 n=1 或 n=2 的情况
如果直接进入循环（比如 for(i=3; i<=n; i++)），当 n=1 时循环条件 3<=1 不成立，result 就没有被赋值，输出会是随机值。所以一定要加 if 判断。
循环次数算错
有些人写 for(int i=1; i<=n; i++) 然后里面做 result = a+b; a = b; b = result;，这样会多算一次。正确应该是从第3项开始，执行 n-2 次。可以这样记忆：已知两项，还需要推 n-2 次才能到第 n 项。
变量更新顺序搞反
```
// 错误写法
a = b;
b = result;
result = a + b;   // 这时候 a 已经被覆盖了！
```
一定要先计算 result，再更新 a 和 b，否则会用到错误的值。
把斐波那契数列从 0 开始记混
有些数学教材定义 F(0)=0, F(1)=1，而兔子问题从1开始。编程时注意根据题目调整初始值。

完整示例：打印前10个月的兔子对数

上面的代码只输出第 n 个月。如果你想看看整个数列的生成过程，可以稍加改造：

#include <iostream>
using namespace std;

int main() {
    int a = 1, b = 1;                       // 前两月
    cout << "前10个月的兔子对数为：" << endl;
    cout << a << " " << b << " ";           // 先打印前两个

    for (int i = 3; i <= 10; i++) {
        int next = a + b;                   // 当前项
        cout << next << " ";
        a = b;                              // 向前滚动
        b = next;
    }
    cout << endl;
    return 0;
}

输出：

前10个月的兔子对数为：
1 1 2 3 5 8 13 21 34 55