遞迴函數核心概念與經典範例總覽

什麼是遞迴？

函數直接或間接呼叫自身**的程式設計技術。將大問題分解為結構相同的子問題，直到達到**基礎情況** 直接求解。

遞迴三要素

經典範例 1：階乘

unsigned long long factorial(unsigned int n) {
    if (n <= 1) return 1;          // 基礎情況
    return n * factorial(n - 1);   // 遞迴步驟 + 合併
}

經典範例 2：費波那契數列 (朴素遞迴效能差)

unsigned long long fib(unsigned int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);  // 指數級重複計算
}

優化**：備忘錄 (Memoization) / 動態規劃 / 矩陣快速冪 → O(log n)。

經典範例 3：漢諾塔

void hanoi(int n, char from, char aux, char to) {
    if (n == 1) {
        printf("移動圓盤 1 從 %c 到 %c\n", from, to);
        return;
    }
    hanoi(n - 1, from, to, aux);           // 將 n-1 移至輔助柱
    printf("移動圓盤 %d 從 %c 到 %c\n", n, from, to); // 移動最大圓盤
    hanoi(n - 1, aux, from, to);           // 將 n-1 從輔助移至目標
}

遞迴 vs 迭代

尾遞迴優化 (TCO)

/* 尾遞迴：遞迴呼叫是函數**最後一個動作** */
int fact_tail(int n, int acc) {
    if (n <= 1) return acc;
    return fact_tail(n - 1, n * acc);  // 無後續運算，編譯器可優化為跳轉
}

/* GCC/Clang -O2 會將尾遞迴優化為迭代，不增長堆疊 */

C 標準**不保證** TCO，但主流編譯器釋出優化模式下均支援。

常見陷阱

1. 堆疊溢位：遞迴深度過大 (如 `fib(50)` 朴素版) → 改迭代或增加堆疊 (`ulimit -s` / 編譯器選項)。
2. 重複計算：費波那契、編輯距離等重疊子問題 → 加入快取 (陣列/雜湊表)。
3. 基礎情況錯誤：`n == 0` vs `n <= 1` 邊界未覆蓋 → 無限遞迴。
4. 參數未縮小：遞迴呼叫傳入相同/更大參數 → 永不收斂。

除錯技巧

/* 印出遞迴深度輔助理解 */
void debug_recursive(int n, int depth) {
    printf("%*s呼叫 f(%d)\n", depth*2, "", n);
    if (n <= 1) return;
    debug_recursive(n-1, depth+1);
}

結語

遞迴是**分治思想**的代碼體現。掌握基礎情況、遞迴步驟、合併結果三要素，警惕堆疊深度、重複計算、尾遞迴優化機會，能寫出優雅且正確的遞迴演算法。實務中：**樹/圖遍歷首選遞迴，線性累加首選迭代，重疊子問題加備忘錄。**