C語言遞歸編程精髓：棧幀機制、終止條件與經典實戰模式

遞歸：函數調用自身的藝術

遞歸將問題分解為相同性質的子問題，通過函數調用自身求解。理解遞歸必須理解運行時棧。

一、棧幀：遞歸的物理基礎

1. 函數調用棧幀結構

高地址
┌─────────────────┐
│  調用者棧幀     │ ← 返回地址、實參、保存的寄存器
├─────────────────┤
│  被調用者棧幀   │ ← 形參、局部變量、返回地址
├─────────────────┤
│     ...         │
├─────────────────┤
│  遞歸第 n 層    │
├─────────────────┤
│  遞歸第 1 層    │
└─────────────────┘
低地址

2. 遞歸下降與回溯

• 下降：每次調用分配新棧幀，參數/局部變量獨立副本。
• 回溯：基例觸發返回，棧幀依次彈出，結果向上傳遞。

3. 關鍵認知

• 每層調用擁有獨立的參數與局部變量空間，互不干擾。
• 靜態/全局變量共享，遞歸中修改需極度謹慎。
• 棧空間有限 (通常 1-8MB)，深度遞歸導致棧溢出。

二、遞歸三要素：基例、遞歸步驟、縮小問題

return_type func(params) {
    if (base_case) return base_value;     // 1. 終止條件
    // 2. 縮小問題規模
    // 3. 遞歸調用
    return combine(func(smaller_params)); // 組合結果
}

三、經典入門：倒序輸出 5~1

void countdown(int n) {
    if (n == 0) return;       // 基例
    printf("%d ", n);         // 當前層工作
    countdown(n - 1);         // 遞歸步驟：問題規模 -1
}
// 輸出: 5 4 3 2 1

四、返回值遞歸：求和 1+2+...+100

int sum(int n) {
    if (n == 1) return 1;     // 基例
    return n + sum(n - 1);    // 遞歸關係：sum(n) = n + sum(n-1)
}
// sum(100) = 5050

等價迭代：

int sum_iter(int n) {
    int s = 0;
    for (int i = 1; i <= n; i++) s += i;
    return s;
}

五、尾遞歸優化 (TCO) 與累加器模式

尾調用：遞歸調用是函數最後一個動作，無需保留當前棧幀。編譯器可優化為跳轉 (O(1) 棧空間)。

// 非尾遞歸：返回後還需加 n
int sum(int n) { return n + sum(n-1); }

// 尾遞歸：引入累加器參數
int sum_tail(int n, int acc) {
    if (n == 0) return acc;
    return sum_tail(n - 1, acc + n); // 尾調用
}
// 調用: sum_tail(100, 0)

GCC/Clang -O2 可優化尾遞歸，MSVC 支持有限。

六、進階模式：分治與樹形遞歸

1. 二分查找 (分治)

int binary_search(int *a, int l, int r, int target) {
    if (l > r) return -1;
    int m = l + (r - l) / 2;
    if (a[m] == target) return m;
    if (a[m] < target) return binary_search(a, m+1, r, target);
    return binary_search(a, l, m-1, target);
}

2. 斐波那契 (樹形遞歸，指數複雜度)

int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2); // 大量重複計算
}
// 優化：備忘錄/動態規劃/矩陣快速冪

3. 目錄遍歷 (系統級遞歸)

void list_dir(const char *path, int depth) {
    DIR *d = opendir(path);
    struct dirent *e;
    while ((e = readdir(d))) {
        if (strcmp(e->d_name, ".") == 0 || strcmp(e->d_name, "..") == 0) continue;
        printf("%*s%s\n", depth*2, "", e->d_name);
        char sub[1024];
        snprintf(sub, sizeof(sub), "%s/%s", path, e->d_name);
        struct stat st;
        if (stat(sub, &st) == 0 && S_ISDIR(st.st_mode))
            list_dir(sub, depth+1);
    }
    closedir(d);
}

七、遞歸 vs 迭代：選擇指南

八、避坑指南

• ✅ 必須有基例，且必然可達。
• ✅ 參數單調變化向基例收斂。
• ✅ 局部變量用於隔離狀態，避免靜態/全局變量。
• ✅ 深度遞歸改迭代或顯式棧。
• ❌ 缺少基例 → 無限遞歸 → Stack Overflow。
• ❌ 參數不變/反向 → 永不終止。
• ❌ 修改共享靜態變量 → 層間干擾。

總結

遞歸是「以問題定義問題」的強大抽象。理解棧幀機制，掌握基例-縮小-組合三部曲，善用尾遞歸與累加器，能優雅解決樹、圖、分治、回溯等結構性問題。但請時刻警惕棧深度，必要時轉迭代或顯式棧實現。

1. 上一篇文章： C語言預處理器完全指南：宏、條件編譯與文件包含最佳實踐
2. 下一篇文章： C語言變量作用域與存儲類別：從自動到靜態的生命週期全景

關於C語言

個人開發框架總結（三）：BaseEditForm 資料編輯視窗基類設計與核心虛擬方法

BaseEditForm 核心成員 屬性 Info：修改模

C語言經典習題：輾轉相除法求最大公約數與最小公倍數

題目描述 輸入兩正整數 m, n，求最大公約數 (GCD)

C 語言 malloc 內存分配器實現原理深度解析

K&R malloc 實現核心邏輯全解析 《C 程序設計語言

WPF/Silverlight 遊戲開發教程 (二十二-1)：重構啟動 — 統一代碼風格、引入 CSS 思維、消除磁盤碎片化代碼

第 21 節模式大變身雖表面游刃有餘，但代碼內部日益鬆散、結