Ackermann 函數：遞歸極限與編譯器優化測試

函數定義

Ackermann 函數是雙參數遞歸函數，增長極快，遞歸深度極大，常用於測試編譯器對尾遞歸優化、棧幀管理能力。

朴素遞歸實現（C）

#include <stdio.h>

int ackerman(int m, int n) {
    if (m == 0) return n + 1;
    if (n == 0) return ackerman(m - 1, 1);
    return ackerman(m - 1, ackerman(m, n - 1));
}

int main() {
    int m, n;
    scanf("%d %d", &m, &n);
    printf("%d", ackerman(m, n));
    return 0;
}

現象與分析

• ackerman(4, 2) 即導致棧溢出崩潰（數值超 19000 位，遞歸調用數億次）。
• 朴素遞歸無法處理 m >= 4 的情況。
• 優化方向：尾遞歸消除、迭代化、手動棧模擬、備忘錄/動態規劃（但參數空間巨大）。

本文僅作入門介紹，深度優化留待進階探討。