首页 > 编程笔记 > C++笔记 阅读:2,810

C++斐波那契数列(递归实现)

以意大利数学家列奥纳多•斐波那契命名的斐波那契数列形式如下:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, …

请注意,在第二个数字之后,序列中的每个数字都是前两个数字的和。斐波那契数列可以定义为:

F0 = 0,
F1 = 1,
FN = FN-1 + FN-2 对于所有 N≥2

很明显,计算除前两个数之外的斐波那契数的问题可以简化为计算两个前置斐波纳契数的问题。下面是计算斐波那契数列中第 n 个数的递归 C++ 函数:
int fib(int n)
{
    if (n <= 0)    //基本情况
        return 0;
    else if (n == 1) // 基本情况
        return 1;
    else
        return fib(n - 1) + fib(n - 2);
}
下面的程序演示了该函数的应用,它显示了前 10 个斐波那契数列中的数字:
// This program demonstrates a recursive function that calculates Fibonacci numbers.
#include <iostream>
using namespace std;

int fib(int); // Function prototype
int main()
{
    cout << "The first 10 Fibonacci numbers are: \n";
    for (int x = 0; x < 10; x++)
        cout << fib(x) << " ";
    cout << endl;
    return 0;
}
int fib (int n)
{
    if (n <= 0) //base case
        return 0;
    else if (n == 1) //base case
        return 1;
    else
        return fib(n - 1) + fib(n - 2);
}
程序输出结果:

The first 10 Fibonacci numbers are:
0 1 1 2 3 5 8 13 21 34

爱面试的程序媛,一个分享面试经验的公众号。跟着站长一起学习,每天都有进步。

通俗易懂,深入浅出,定时分享程序员面试的那点事。

面试如何造火箭?工作如何拧螺丝?都在这个公号哦。

扫描二维码关注公众号,免费领取价值 1000 元的求职面试资料(限时免费)!

当你决定关注「爱面试的程序媛」,你已然超越了90%的程序员!

爱面试的程序媛二维码
微信扫描二维码关注