C++斐波那契数列（递归实现）

发布时间：2020-12-16 07:37:02 所属栏目：百科来源：网络整理

导读：以意大利数学家列奥纳多?斐波那契命名的斐波那契数列形式如下： 0,1,2,3,5,8,13,21,34,55,89,144,233,… 请注意，在第二个数字之后，序列中的每个数字都是前两个数字的和。斐波那契数列可以定义为： F 0 = 0, F 1 = 1, F N = F N-1 + F N-2 对于所有 N≥2 很

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

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

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

F₀ = 0,
F₁ = 1,
F_N = F_N-1 + F_N-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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!