深度解析：函數遞歸與堆疊幀的底層關係

從反組譯看遞歸本質

以階乘遞歸為例，觀察 MSVC Debug 版反組譯碼：

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

主程式呼叫

; main 中呼叫 factorial(4)
push 4
call @ILT+475(_factorial)
add esp, 4
mov [fact], eax

factorial 函數序言/尾聲

factorial:
push ebp
mov ebp, esp
sub esp, 0C0h          ; 配置堆疊幀空間 (含安全檢查填充 0xCC)
push ebx; push esi; push edi
lea edi, [ebp-0C0h]
mov ecx, 30h
mov eax, 0CCCCCCCCh
rep stos dword ptr es:[edi]  ; 填充 0xCC 偵測堆疊溢位

; 遞歸基底案例
cmp dword ptr [n], 1
jne RECURSIVE_CASE
mov eax, 1
jmp EPILOGUE

RECURSIVE_CASE:
mov eax, [n]
sub eax, 1
push eax                ; 參數 n-1 入堆
call @ILT+475(_factorial) ; 遞歸呼叫自己
add esp, 4
imul eax, [n]           ; eax = (n-1)! * n

EPILOGUE:
pop edi; pop esi; pop ebx
add esp, 0C0h
cmp ebp, esp
call @ILT+320(__RTC_CheckEsp)
mov esp, ebp
pop ebp
ret

關鍵觀察

1. 每次遞歸 = 新堆疊幀：push ebp / mov ebp, esp / sub esp, ... 建立獨立作用域。
2. 參數傳遞：push eax 將 n-1 壓入呼叫者堆疊，被呼叫者從 [ebp+8] 取用。
3. 返回值：eax 傳遞 (n-1)!，呼叫者 imul 乘上 n。
4. 堆疊幀銷毀：mov esp, ebp / pop ebp / ret 精確還原呼叫者堆疊指標。
5. 系統自動管理：編譯器插入的序言/尾聲、安全檢查（0xCC 填充、__RTC_CheckEsp）保證堆疊平衡。

手動模擬堆疊實現遞歸（非遞歸版階乘）

#include "stack.h"  // 假設提供 StackNode, CreateStack, Push, Pop
#define MAX_STACK 100

int main() {
    StackNode* stk = CreateStack(MAX_STACK);
    int n, tmp = 1, result = 1;

    printf("Input n: "); scanf("%d", &n);

    // 1. 參數入堆：n, n-1, ..., 1
    while (n > 0) Push(stk, n--);

    // 2. 出堆累乘：1 * 2 * 3 * ... * n
    while (stk->top) {
        Pop(stk, &tmp);
        result *= tmp;
    }

    printf("%d! = %d\n", n, result);
    return 0;
}

此版本將「系統呼叫堆疊」顯式化為「資料結構堆疊」，本質相同：遞歸 = 隱式堆疊 + 函數呼叫慣例。

遞歸深度限制與堆疊溢位

• 典型預設堆疊 1~8 MB（Windows 1 MB，Linux 8 MB）。
• 每幀約 32~128 位元組（含保存暫存器、區域變數、對齊填充）。
• 最大安全深度約 1MB / 64B ≈ 16,000 層；超過即 Stack Overflow。
• 解決方案：尾遞歸優化（編譯器支援）、改迭代、增大堆疊（ulimit -s、/STACK 連結旗標）、分治降低深度。

總結

1. 函數遞歸本質是作業系統/執行環境提供的呼叫堆疊的自動化使用。
2. 反組譯碼揭示了參數傳遞、返回值、堆疊幀建立/銷毀的完整流程。
3. 理解堆疊幀機制有助於除錯遞歸錯誤、優化深度、實現協程/綠色執行緒。
4. 手動堆疊模擬是理解遞歸本質的最佳練習，也是編譯器實現尾遞歸優化的基礎。