C++ 斐波那契数列

斐波那契数列是编程练习中非常经典的数列。它的生成规律很简单：第 0 项是 0，第 1 项是 1，从第 2 项开始，每一项都等于它前面相邻两项之和。

按照这个规则，斐波那契数列的前 10 项依次如下：

0  1  1  2  3  5  8  13  21  34 ...

比如第 2 项等于 0 + 1 = 1，第 3 项等于 1 + 1 = 2，第 4 项等于 1 + 2 = 3，后面的数字以此类推。在 C++ 中，我们既可以使用循环一步步往后推算，也可以使用递归函数来实现。

使用 for 循环生成斐波那契数列

仔细观察斐波那契数列的递推过程可以发现：不管往后推算多少项，我们在每一轮真正需要记住的其实只有相邻的两个数，不妨记作 a 和 b。

一开始，我们让 a = 0、b = 1。在每一轮 for 循环中，我们先输出左边的 a，再通过 a + b 算出后面的新项 next。算完之后，把原来的 b 赋给 a，再把刚算出来的 next 赋给 b。前 5 轮的变量变化如下表所示。

小伙伴们可以把 a 和 b 看成一个不断向右滑动的 “两格小窗口”：每算出一个新数字，窗口就整体往右挪一格。

下面我们把这个滚动更新的过程写成代码，输出斐波那契数列的前 10 项。

示例 1：循环输出前 10 项

#include <iostream>

int main() {
    int count = 10;                // 输出的项数
    long long a = 0;               // 第 0 项
    long long b = 1;               // 第 1 项

    for (int i = 0; i < count; i++) {
        std::cout << a << " ";
        long long next = a + b;    // 计算后面的新项
        a = b;                     // a 更新为原来的 b
        b = next;                  // b 更新为刚算出的 next
    }
    std::cout << '\n';
    return 0;
}

运行结果如下。

0 1 1 2 3 5 8 13 21 34

分析：

在上面例子中，每一轮循环一上来先输出的是 a，而不是刚算出来的 next。这样写可以把最开头的 0 和 1 也统一放在循环里打印，省去了在循环外单独输出的麻烦。

另外，斐波那契数列往后增长得非常快，算到第 47 项就会超出 32 位 int 的表示范围。因此在选择数据类型时，我们使用了取值范围更大的 long long 来保存每一项。

在更新变量时，小伙伴们要特别留意 a = b; 和 b = next; 的先后顺序。如果把这两句颠倒过来，下面这种写法就是错误的：

long long next = a + b;
b = next;    // 先覆盖了 b 的旧值
a = b;       // a 也会变成 next

一旦先把 next 赋给 b，b 原来的旧值就被覆盖掉了。紧接着执行 a = b; 时，a 拿到的也是 next，后面算出来的数字就会全部翻倍出错。

使用递归函数生成斐波那契数列

除了使用循环，我们也可以对照斐波那契数列的数学定义，编写递归函数来求解。具体规则很直接：当 n <= 1 时直接返回 n，也就是第 0 项返回 0、第 1 项返回 1。当 n >= 2 时，函数返回 fibonacci(n - 1) + fibonacci(n - 2)。下面我们来看一个例子。

示例 2：递归输出前 10 项

#include <iostream>

// 递归求斐波那契数列的第 n 项
long long fibonacci(int n) {
    if (n <= 1) {
        return n;    // 0 返回 0，1 返回 1
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    int count = 10;
    for (int i = 0; i < count; i++) {
        std::cout << fibonacci(i) << " ";
    }
    std::cout << '\n';
    return 0;
}

运行结果如下。

0 1 1 2 3 5 8 13 21 34

分析：

fibonacci() 函数把数学递推公式直接写成了代码：开头的 if (n <= 1) 作为终止条件处理第 0 项和第 1 项，其余情况直接返回前两项之和。不过，这种直接递归的写法有一个明显的性能短板：同一个子问题会被翻来覆去重复计算很多遍。

比如当我们调用 fibonacci(5) 时，前几层的展开算式如下：

fibonacci(5) = fibonacci(4) + fibonacci(3)
fibonacci(4) = fibonacci(3) + fibonacci(2)
fibonacci(3) = fibonacci(2) + fibonacci(1)

从算式可以看出，仅仅是求第 5 项，fibonacci(3) 就被算了 2 次，fibonacci(2) 更是被重复算了 3 次。当 n 增大到 40 以上时，重复调用的次数会急剧暴增，程序运行会出现明显的卡顿。

相比之下，前面介绍的 for 循环写法从前往后顺着推算，每一项都只计算一次。它既没有额外的函数调用开销，运行速度也快得多，因此在实际开发中更推荐使用循环写法。