C 語言遞迴輸出費波那契數列前 10 項：完整程式碼與原理詳解

題目要求

• 使用 **C 語言**
• **遞迴** 實作 (不得使用迴圈)
• 輸出費波那契數列前 10 項

費波那契數列定義

F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2) (n>2)

前 10 項：1, 1, 2, 3, 5, 8, 13, 21, 34, 55

遞迴策略：尾遞迴累加器模式

為避免指數級時間複雜度 (朴素遞迴 `fib(n)=fib(n-1)+fib(n-2)` 會重複計算)，採用 **尾遞迴** 攜帶前兩項數值與計數器：

• 參數 `x`：前一項 (F(n-1))
• 參數 `y`：當前項 (F(n))
• 參數 `acc`：已輸出項數計數器

完整程式碼 (含註解)

#include 

/**
 * 尾遞迴輸出費波那契數列
 * @param x  前一項數值 (初始為 1)
 * @param y  當前項數值 (初始為 1)
 * @param acc 已輸出項數 (初始為 1)
 */
void printFibRecursive(int x, int y, int acc) {
    // 終止條件：已輸出 10 項
    if (acc > 10) return;

    // 輸出當前項 (x 代表 F(acc))
    printf("%d ", x);

    // 遞迴呼叫：下一項為 y，再下一項為 x+y，計數器+1
    printFibRecursive(y, x + y, acc + 1);
}

int main() {
    // 起始呼叫：F(1)=1, F(2)=1, 已輸出第 1 項
    printFibRecursive(1, 1, 1);
    printf("\n");
    return 0;
}

執行流程追蹤

輸出結果

1 1 2 3 5 8 13 21 34 55

時間與空間複雜度

• 時間：O(n) — 每項僅計算一次
• 空間：O(n) — 遞迴呼叫堆疊深度 n (編譯器若支援尾呼叫優化可優化為 O(1))

延伸：若需輸出第 n 項 (單一值)

int fib(int n) {
    if (n <= 2) return 1;
    return fib(n-1) + fib(n-2); // 指數複雜度，僅供教學
}

// 尾遞迴優化版
int fibTail(int n, int a, int b) {
    if (n == 1) return a;
    if (n == 2) return b;
    return fibTail(n-1, b, a+b);
}
// 呼叫: fibTail(10, 1, 1) -> 55

總結

使用**尾遞迴累加器模式**可在符合「純遞迴、無迴圈」限制下，以 **O(n) 時間** 高效輸出費波那契數列。關鍵在於將「狀態」 (前兩項值、計數器) 作為參數傳遞，而非依賴全域變數或重複計算。