Fibonacci 費氏數列

在本篇文章中，我們將探討如何透過遞迴（Recursion）來實作 Fibonacci 數列。

Fibonacci 數列簡介

• F(0) = 0
• F(1) = 1
• 當 n ≥ 2 時，F(n) = F(n-1) + F(n-2)

也就是說，Fibonacci 數列的每一項值（從第三項開始）都是前兩項的總和。Fibonacci 數列的前幾項為：

n    :  0   1   2   3   4   5   6   7   8   9  ...
F(n) :  0   1   1   2   3   5   8  13  21  34  ...

程式碼

以下為完整的 C 程式碼範例：

// 遞迴產生 Fibonacci 數列的函式
#include <stdio.h>

// 宣告 fibonacci 函式原型，返回型別為 unsigned long long int
unsigned long long int fibonacci(unsigned int n);

// main 函式，開始程式執行
int main(void)
{
    unsigned long long int result; // 用來儲存 Fibonacci 值
    unsigned int number;           // 用戶輸入的數字

    // 提示用戶輸入整數
    printf("%s", "Enter an integer: ");
    scanf("%u", &number);

    // 計算用戶輸入數字對應的 Fibonacci 值
    result = fibonacci(number);

    // 顯示結果
    printf("Fibonacci(%u) = %llu\n", number, result);
} // end main

// Fibonacci 函式的遞迴定義
unsigned long long int fibonacci(unsigned int n)
{
    // 基本情況：當 n 等於 0 或 1 時，直接回傳 n
    if (0 == n || 1 == n)
    {
        return n;
    }
    // 遞迴情況：計算前兩項的和
    else
    {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
} // end function fibonacci

• 當 n 為 0 或 1 時，直接回傳 n。
• 這就是遞迴的終止條件：不需要再進行任何遞迴呼叫。

• 當 n > 1 時，將回傳 fibonacci(n-1) 與 fibonacci(n-2) 的和。
• 遞迴的運作方式：
  • 為了計算 fibonacci(n)，必須先計算 fibonacci(n-1) 與 fibonacci(n-2)。
  • 計算 fibonacci(n-1) 時，又會進一步呼叫 fibonacci(n-2) 和 fibonacci(n-3)，如此層層展開。
  • 最終都會回到基礎情況 n == 0 或 n == 1，才依序回傳並累加。

以輸入 n = 5 為例，fibonacci(5) 會依照下列遞迴程序執行：

1. fibonacci(5)
2. • → 需要 fibonacci(4) + fibonacci(3)
2. fibonacci(4)
3. • → 需要 fibonacci(3) + fibonacci(2)
3. fibonacci(3)（在 fibonacci(4) 內部呼叫）
4. • → 需要 fibonacci(2) + fibonacci(1)
4. fibonacci(2)（在 fibonacci(3) 內部呼叫）
5. • → 需要 fibonacci(1) + fibonacci(0)
   • fibonacci(1) 回傳 1
   • fibonacci(0) 回傳 0
   • 因此 fibonacci(2) 回傳 1 + 0 = 1
5. 回到 fibonacci(3)：
6. • 另一個呼叫為 fibonacci(1)，直接回傳 1
   • 因此 fibonacci(3) 回傳 1 + 1 = 2
6. 回到 fibonacci(4)：
7. • 已經知道 fibonacci(3) = 2
   • 另一個呼叫 fibonacci(2) 在之前已算出來是 1
   • 因此 fibonacci(4) 回傳 2 + 1 = 3
7. 回到最外層 fibonacci(5)：
8. • 已經知道 fibonacci(4) = 3
   • 需要再計算 fibonacci(3) = 2 (一樣進行遞迴)
   • 最後 fibonacci(5) = 3 + 2 = 5

經過以上遞迴展開，我們得到 Fibonacci(5) = 5。