您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

C語言數據結構：用棧非遞歸實現阿克曼函數

編輯：關於C

問題背景：遞歸的棧溢出風險

阿克曼函數是經典的雙遞歸函數，定義如下：

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)

直接遞歸實現雖然直觀，但調用深度極大。測試發現：當 m=3, n=4 時，若棧大小僅 100 便會溢出。這促使我們尋找非遞歸的棧實現方案。

棧的數據結構定義

typedef int Type;

typedef struct stack {
    Type *base;  // 棧底指針
    Type *top;   // 棧頂指針
    int size;    // 當前分配容量
} Stack, *LinkStack;

#define MAX 10000
#define IN 10
#define ERROR 0
#define OK 1

核心操作函數

初始化與基本操作

void Creat(LinkStack S) {
    S->base = (Type*)malloc(sizeof(Type) * MAX);
    if (!S->base) exit(0);
    S->top = S->base;
    S->size = MAX;
}

int Push(LinkStack S, Type c) {
    // 棧滿自動擴容
    if (S->top - S->base >= S->size) {
        S->base = (Type*)realloc(S->base, sizeof(Type) * (S->size + IN));
        if (!S->base) return ERROR;
        S->top = S->base + S->size;
        S->size += IN;
    }
    *(S->top++) = c;
    return OK;
}

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

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

非遞歸阿克曼函數實現

int Akm(int m, int n) {
    int result = 0;
    Stack S;
    Creat(&S);

    do {
        while (m) {
            while (n) {
                Push(&S, m - 1);  // 保存 m-1
                n -= 1;
            }
            n = 1;
            m -= 1;
        }
        
        if (!Isempty(S)) {
            Pop(&S, &m);
            n += 1;
        }
    } while ((m != 0) || (Isempty(S) != OK));

    return n + 1;
}

遞歸版本對比

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

測試驗證

int main() {
    int m, n, result;
    while (1) {
        scanf("%d%d", &m, &n);
        result = Akm_Recur(m, n);
        printf("遞歸結果: %d  ", result);
        result = Akm(m, n);
        printf("非遞歸結果: %d\n", result);
    }
    return 0;
}