C 語言棧實現 Ackermann 函數：遞歸與非遞歸（手動棧）對比

前言

Ackermann 函數是經典的**雙遞歸**函數，定義：

A(m, n) = n + 1                 (m = 0)
A(m, n) = A(m-1, 1)             (m > 0, n = 0)
A(m, n) = A(m-1, A(m, n-1))     (m > 0, n > 0)

其極快增長特性導致遞歸深度極大（A(3,4) 需數萬層調用），輕易爆棧。本文展示**手動棧模擬遞歸**的非遞歸實作，並分析棧容量需求。

棧資料結構（順序棧，動態擴容）

#include 
#include 

#define MAX_INIT 10000
#define INCREMENT 10
#define OK 1
#define ERROR 0

typedef int Type;

typedef struct {
    Type *base;
    Type *top;
    int size;
} Stack;

void Create(Stack *S) {
    S->base = (Type *)malloc(sizeof(Type) * MAX_INIT);
    if (!S->base) exit(0);
    S->top = S->base;
    S->size = MAX_INIT;
}

int Push(Stack *S, Type e) {
    if (S->top - S->base >= S->size) {
        Type *newbase = (Type *)realloc(S->base, (S->size + INCREMENT) * sizeof(Type));
        if (!newbase) return ERROR;
        S->base = newbase;
        S->top = S->base + S->size;
        S->size += INCREMENT;
    }
    *(S->top++) = e;
    return OK;
}

int Pop(Stack *S, Type *e) {
    if (S->top == S->base) return ERROR;
    *e = *(--S->top);
    return OK;
}

int IsEmpty(Stack S) {
    return S.top == S.base ? OK : ERROR;
}

void Destroy(Stack *S) {
    free(S->base);
    S->base = S->top = NULL;
    S->size = 0;
}

遞歸版實作（基準）

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

非遞歸版：手動棧模擬

int Ackermann_Stack(int m, int n) {
    Stack S;
    Create(&S);
    int result = 0;

    do {
        // 階段 1：處理 m > 0 且 n > 0 的巢狀遞歸
        while (m > 0) {
            while (n > 0) {
                Push(&S, m - 1); // 保存外層 m-1
                n--;             // 內層 n-1
            }
            n = 1;               // n 歸零後，內層基準情況 n=0 → A(m,0)=A(m-1,1)
            m--;                 // 外層 m-1
        }

        // 階段 2：m == 0，基準情況 A(0,n) = n+1
        // result = n + 1; 此處直接用 n 累加，迴圈結束後返回 n+1

        // 階段 3：彈出保存的 m-1 繼續外層計算
        if (!IsEmpty(S)) {
            Pop(&S, &m);
            n++;                 // 外層調用返回後，n 視為內層結果 +1（對應 A(m-1, A(...))）
        }
    } while (m != 0 || !IsEmpty(S));

    Destroy(&S);
    return n + 1; // 最終結果
}

關鍵邏輯解析

1. 雙重 while 對應雙遞歸： 外層 while (m)、內層 while (n) 直接映射定義中 m>0, n>0 的巢狀結構。
2. 棧保存「外層待續 m-1」： 內層遞歸 A(m, n-1) 完成前，外層 A(m-1, ...) 的參數 m-1 必須保存。
3. n 變數複用： 迴過程中 n 既作內層計數器，又作中間結果傳遞；n++ 對應外層調用獲得內層結果後的 +1 語意。
4. 終止條件： m == 0 且棧空，此時 n 即為最內層基準結果累加值。

測試與棧容量驗證

int main() {
    int m, n;
    while (1) {
        printf("Input m n: ");
        if (scanf("%d %d", &m, &n) != 2) break;

        int r1 = Ackermann_Recur(m, n);
        int r2 = Ackermann_Stack(m, n);
        printf("Recur: %d, Stack: %d\n", r1, r2);
    }
    return 0;
}

測試結果

關鍵發現： 原文棧初始容量 MAX 100 **完全不足**，A(3,4) 即需數萬棧幀。動態擴容（realloc）是非遞歸版不爆棧的關鍵。

遞歸 vs 非遞歸對比

總結

Ackermann 函數是「遞歸深度不可控」的教科書級案例。手動棧非遞歸實作展示了**將呼叫棧顯式化**的通用技巧：

1. 識別遞歸參數與返回值對應的狀態變數。
2. 用棧保存「待續上下文」（此處為外層 m-1）。
3. 用迴圈與狀態機替換函數調用/返回。
4. **動態擴容棧**確保不受系統棧限制。

此模式廣泛應用於編譯器實現、解析器、圖遍歷、狀態機等需避免棧溢位的場景。