C++斐波那契數列（遞迴實現）

以意大利數學家列奧納多•斐波那契命名的斐波那契數列形式如下：

0, 1, 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