深度解析：函式遞迴與堆疊的底層關係——從反組譯碼到手寫堆疊實現

前言

遞迴是程式設計的強大工具，但其底層如何運作？本文透過 Visual Studio 反組譯碼 分析階乘遞迴的堆疊幀變化，並展示如何用手寫堆疊替代系統遞迴，深入理解「遞迴本質是堆疊操作」。

實驗環境與程式碼

/* factorial.c */
#include 

int factorial(int n);

int main() {
    int fact = factorial(4);
    printf("%d\n", fact);  // 24
    return 0;
}

int factorial(int n) {
    if (1 == n) return 1;
    return n * factorial(n - 1);
}

反組譯碼分析（關鍵片段）

main 呼叫 factorial(4)

; main 內部
push    4                ; 參數入堆疊
call    _factorial       ; 呼叫函式
add     esp, 4           ; 清理參數堆疊空間
mov     [fact], eax      ; 返回值在 eax

factorial 函式序言與尾聲

_factorial:
push    ebp              ; 保存舊堆疊幀指標
mov     ebp, esp         ; 建立新堆疊幀
sub     esp, 0C0h        ; 分配區域變數空間
...                      ; 保存暫存器 ebx/esi/edi
lea     edi, [ebp-0C0h]
mov     ecx, 30h
mov     eax, 0CCCCCCCCh
rep stos dword ptr es:[edi]  ; 0xCC 填充（Debug 模式偵測未初始化）

; 核心遞迴邏輯
cmp     dword ptr [n], 1
jne     L_recursive
mov     eax, 1           ; 基底案例：返回 1
jmp     L_epilogue

L_recursive:
mov     eax, [n]
sub     eax, 1
push    eax              ; 參數 n-1 入堆疊
call    _factorial       ; 遞迴呼叫自己
add     esp, 4           ; 清理參數
imul    eax, [n]         ; eax *= n  (累乘)

L_epilogue:
pop     edi / pop esi / pop ebx
add     esp, 0C0h        ; 釋放區域空間
cmp     ebp, esp
call    __RTC_CheckEsp   ; 堆疊平衡檢查
mov     esp, ebp
pop     ebp
ret

堆疊幀演變圖解（factorial(4)）

關鍵觀察

• 參數傳遞：呼叫端 push 參數，被呼叫端 [ebp+8] 存取（x86 cdecl 慣例）
• 返回值：放在 eax，遞迴回溯時逐層 imul 累乘
• 堆疊幀鏈：ebp 串聯所有幀，ret 彈出返回位址並跳轉
• 系統自動管理：編譯器生成序言/尾聲，程式設計師無感知

手寫堆疊模擬遞迴

既然遞迴本質是「先進後出」的參數堆疊與回溯運算，我們可以用顯式堆疊資料結構替代。

/* stack_factorial.c */
#include 
#include 

#define MAX_STACK 100

typedef struct {
    int data[MAX_STACK];
    int top;
} Stack;

void push(Stack *s, int val) { s->data[s->top++] = val; }
int pop(Stack *s) { return s->data[--s->top]; }
int empty(Stack *s) { return s->top == 0; }

int main() {
    Stack st = {.top = 0};
    int n, tmp = 1, result = 1;

    printf("輸入階乘 n: "); scanf("%d", &n);
    while (n > 0) push(&st, n--);  // 入堆疊：n, n-1, ..., 1

    while (!empty(&st)) {
        tmp = pop(&st);            // 出堆疊：1, 2, ..., n
        result *= tmp;             // 累乘
    }
    printf("%d! = %d\n", n, result);
    return 0;
}

對比總結

延伸閱讀

• 函式呼叫堆疊幀完整操作詳解
• 尾遞迴優化（Tail Call Optimization）：編譯器將尾部遞迴轉為迴圈
• 延續傳遞風格（CPS）與蹦床函式實現無限遞迴不溢位

結語

透過反組譯碼觀察遞迴的堆疊幀建立、參數傳遞、回溯運算全過程，能將「遞迴」從魔法變為可視化的機制。手寫堆疊實現進一步證明：遞迴 = 隱式堆疊 + 回溯邏輯。理解這一點，除錯棧溢位、優化效能、設計非遞迴演算法都將更得心應手。