您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> C 語言入門

C 語言遞迴程式設計精要：從階乘、費波那契到遞迴深度與效能優化

編輯：C 語言入門

C 語言遞迴程式設計精要

遞迴是一種「以自身定義自身」的程式設計技巧。在 C 語言中，函式可直接或間接呼叫自己，將複雜問題分解為相同性質的子問題。本文從基礎語法切入，透過經典數學範例深入剖析遞迴運作機制、終止條件設計、效能陷阱與優化策略。

遞迴三要素：基礎案例、遞迴關係、終止條件

void recursion() {
    recursion(); // 直接遞迴：缺少終止條件會導致無限遞迴 → 堆疊溢位
}

int main() {
    recursion();
    return 0;
}

鐵律：每個遞迴函式必須包含明確的終止條件，否則程式將耗盡呼叫堆疊而崩潰。

經典範例一：階乘計算

#include <stdio.h>

unsigned long long factorial(unsigned int n) {
    if (n <= 1) return 1;           // 終止條件：基礎案例
    return n * factorial(n - 1);    // 遞迴關係：n! = n × (n-1)!
}

int main() {
    for (int i = 0; i <= 15; i++) {
        printf("%2d! = %llu\n", i, factorial(i));
    }
    return 0;
}

執行追蹤 (factorial(4))：

factorial(4)
→ 4 * factorial(3)
→ 4 * (3 * factorial(2))
→ 4 * (3 * (2 * factorial(1)))
→ 4 * (3 * (2 * 1)) = 24

經典範例二：費波那契數列

#include <stdio.h>

int fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    for (int i = 0; i < 10; i++) {
        printf("F(%d) = %d\n", i, fibonacci(i));
    }
    return 0;
}

效能警示：朴素遞迴實作時間複雜度為 O(2^n)，重複計算極多。fibonacci(40) 已需秒級時間。

遞迴 vs 迭代：效能與記憶體權衡

維度	遞迴	迭代
程式碼簡潔度	高（符合數學定義）	中（需手動管理狀態）
記憶體使用	O(n) 堆疊幀	O(1) 常數空間
執行速度	較慢（函式呼叫開銷）	較快
適用場景	樹/圖遍歷、分治演算法、回溯法	簡單線性計算、效能敏感場合

遞迴優化三大絕招

1. 尾遞迴優化

若遞迴呼叫是函式的最後一個動作，編譯器可將其轉換為迴圈，消除堆疊增長：

// 尾遞迴版階乘
unsigned long long fact_tail(unsigned int n, unsigned long long acc) {
    if (n <= 1) return acc;
    return fact_tail(n - 1, acc * n); // 遞迴呼叫為最後操作
}

// 包裝函式
unsigned long long factorial(unsigned int n) {
    return fact_tail(n, 1);
}

gcc -O2、clang -O2 均可自動優化尾遞迴。

2. 備忘錄 / 動態規劃

針對重疊子問題（如費波那契），緩存已計算結果：

#include <stdio.h>
#define MAX 100
long long memo[MAX];

long long fib_memo(int n) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    return memo[n] = fib_memo(n - 1) + fib_memo(n - 2);
}

時間複雜度從 O(2^n) 降為 O(n)，空間換時間的經典典範。

3. 手動模擬堆疊（消除遞迴）

對於極深遞迴（如檔案系統遍歷），改用動態陣列模擬堆疊：

typedef struct { int n; int state; } Frame;
Frame stack[10000];
int top = 0;

void fib_iterative(int n) {
    stack[top++] = (Frame){n, 0};
    while (top > 0) {
        Frame *f = &stack[top - 1];
        if (f->n <= 1) { /* 處理基礎案例 */ top--; }
        else if (f->state == 0) { f->state = 1; stack[top++] = (Frame){f->n - 1, 0}; }
        else if (f->state == 1) { f->state = 2; stack[top++] = (Frame){f->n - 2, 0}; }
        else { /* 合併結果 */ top--; }
    }
}