深入理解遞迴與堆疊：從函數呼叫機制到手動模擬遞迴

前言

遞迴本質是函數呼叫自身。理解遞迴必須先理解呼叫堆疊。本文從一般函數呼叫堆疊佈局切入，分析遞迴堆疊增長，並示範如何用顯式堆疊消除遞迴，解決堆疊溢位風險。

1. 一般函數呼叫的堆疊模型

假設 A() → B() → C()，堆疊由高址向低址增長：

高址
+----------------+
|   main()       |
|   process()    |
|   iterate(6)   |  ← 最新呼叫
|   iterate(5)   |
|   iterate(4)   |
|   iterate(3)   |
|   iterate(2)   |
|   iterate(1)   |  ← 基底案例
+----------------+
低址

每個堆疊幀包含：回傳位址、參數、區域變數、儲存的暫存器（如 EBP）。

2. 遞迴函數的堆疊演進

例：計算 1+2+...+n

int iterate(int n)
{
    if (n == 1) return 1;          /* 基底案例：出口 */
    return n + iterate(n - 1);     /* 遞迴策略：縮小問題 */
}

呼叫 iterate(6) 產生 6 個堆疊幀，n=1 時開始回傳，層層累加。

3. 遞迴的兩大關鍵要素

1. 遞迴策略：如何將問題縮小（如 n-1）。
2. 出口條件：何時停止遞迴（如 n==1）。

缺一不可，否則無限遞迴導致堆疊溢位。

4. 堆疊深度限制

執行緒預設堆疊通常 1~8 MB。若遞迴深度過大（如 10⁵ 層），會耗盡堆疊導致崩潰。此時必須改寫為迴圈或顯式堆疊。

5. 以顯式堆疊模擬遞迴

將「待處理任務」推入堆疊，迴圈取出處理：

/* 以動態陣列實作簡易堆疊 */
typedef struct { int *data; int top, capacity; } Stack;

void stack_push(Stack *s, int val) { /* 略 */ }
int  stack_pop(Stack *s) { /* 略 */ }
int  stack_empty(const Stack *s) { return s->top == 0; }

int iterate_iterative(int n)
{
    Stack st = { malloc(sizeof(int) * n), 0, n };
    int sum = 0;
    stack_push(&st, n);

    while (!stack_empty(&st)) {
        int cur = stack_pop(&st);
        sum += cur;
        if (cur > 1) stack_push(&st, cur - 1);
    }
    free(st.data);
    return sum;
}

此法將呼叫堆疊轉為資料堆疊，受限於堆積記憶體而非呼叫堆疊，深度可控。

6. 總結

• 遞迴 = 函數自我呼叫 = 隱式使用呼叫堆疊。
• 所有遞迴皆可轉為迴圈 + 顯式堆疊（等價性）。
• 實務上：淺層遞迴（< 1000 層）直接用遞迴碼碼可讀性高；深層/不確定深度必須改迴圈或顯式堆疊。
• 編譯器最佳化（尾端遞迴消除）可自動將特定遞迴轉為迴圈，但不應依賴。