C++ 實現斐波那契數列：遞歸與迭代的高效解法

斐波那契數列簡介

斐波那契數列是一個經典的數學序列，其定義為：前兩項為 1，從第三項開始每一項都等於前兩項之和。即 F(0)=1, F(1)=1, F(n)=F(n-1)+F(n-2) (n≥2)。該數列在計算機科學、數學建模、算法設計等領域有廣泛應用。

C++ 實現方案

本文提供一個基於靜態數組緩存的迭代實現，避免了遞歸的重複計算開銷，時間複雜度為 O(n)，空間複雜度為 O(1)（固定大小緩存）。

核心代碼

#include <iostream>
#include <cassert>
#include <cstdlib>

const int MAX_SIZE = 100;

int* fibonacci(int n) {
    static int cache[MAX_SIZE] = {0}; // 靜態數組自動初始化為 0
    assert(n > 0);
    
    // 基礎情況
    cache[0] = cache[1] = 1;
    
    // 尋找第一個未計算的位置
    int i = 0;
    while (i < MAX_SIZE && cache[i] != 0) ++i;
    
    // 迭代填充數組
    while (i <= n && i < MAX_SIZE) {
        cache[i] = cache[i-1] + cache[i-2];
        ++i;
    }
    return cache;
}

int main() {
    int n = 0;
    std::cout << "請輸入要計算的斐波那契數項數: ";
    std::cin >> n;
    
    int* result = fibonacci(n);
    for (int i = 0; i < n; ++i) {
        std::cout << result[i] << " ";
    }
    std::cout << std::endl;
    
    system("pause"); // Windows 環境下暫停控制台
    return 0;
}

關鍵點解析

• 靜態數組緩存：使用 static int cache[MAX_SIZE] 保持函數調用之間的狀態，避免重複計算。
• 斷言檢查：assert(n > 0) 確保輸入合法性。
• 邊界保護：循環條件 i < MAX_SIZE 防止數組越界。
• 迭代優於遞歸：消除了遞歸調用棧開銷，顯著提升大 n 時的性能。

進階優化方向

若需計算極大項數（超出 int 範圍），可結合 矩陣快速冪（O(log n)）或 大整數庫（如 Boost.Multiprecision）實現任意精度計算。