Ackerman的递归与非递归算法

　　已知Ackerman函数的定义如下：
akm(m,n)=⎧⎩⎨n+1,akm(m−1,1),akm(m−1,akm(m,n−1)),m = 0m≠0,n=0m≠0,n≠0
请设计对应的递归算法和非递归算法。
1)递归算法:

//Ackerman递归算法
int akm1(int m,int n){
int q;
if(m==0)
return n+1;
else if(n==0)
return akm1(m-1,1);
else{
        q=akm1(m,n-1);
return akm1(m-1,q);
    }

}

2)非递归算法

//Ackerman非递归算法
int akm2(int m,int n){
    struct{
        int vm,vn; //分别保存m和n值
        int vf; //保存akm(m,n)值
        int tag; //标识是否求出akm(m,n)值，1:表示未求出，0:表示已求出
    }St[MaxSize];

    int top=-1; //栈指针
    top++; //初值进栈
St[top].vm=m; St[top].vn=n; St[top].tag=1;
    while(top > -1){   //栈不空时循环
        if (St[top].tag==1)   //未计算出栈顶元素的vf值
        { 
            if (St[top].vm==0)      //(1)式
            {
St[top].vf=St[top].vn+1;
St[top].tag=0;
            } 
            else if (St[top].vn==0) //(2)式
            {
                top++;
St[top].vm=St[top-1].vm-1;
St[top].vn=1;
St[top].tag=1;
            }
            else                    //(3)式
            {
                top++;
St[top].vm=St[top-1].vm;
St[top].vn=St[top-1].vn-1;
St[top].tag=1;
            }
        }
        else if (St[top].tag==0)  //已计算出vf值
        {
            if (top>0 && St[top-1].vn==0) //(2)式
            {
St[top-1].vf=St[top].vf;
St[top-1].tag=0;
                top--;
            }
            else if (top > 0) //(3)式
            {
St[top-1].vm=St[top-1].vm-1;
St[top-1].vn=St[top].vf;
St[top-1].tag=1;
                top--;
            }
        }
        if(top==0 && St[top].tag==0) //栈中只有一个已求出vf的元素时退出循环
break;
    }
    return St[top].vf;

}

完整代码如下：

#include <stdio.h>
#define MaxSize 100

//Ackerman递归算法
int akm1(int m,int n){
    int q;
    if(m==0)
        return n+1;
    else if(n==0)
        return akm1(m-1,1);
    else{
        q=akm1(m,n-1);
        return akm1(m-1,q);
    }

}

//Ackerman非递归算法
int akm2(int m,int n){
    struct{
        int vm,vn; //分别保存m和n值
        int vf; //保存akm(m,n)值
        int tag; //标识是否求出akm(m,n)值，1:表示未求出，0:表示已求出
    }St[MaxSize];

    int top=-1; //栈指针
    top++; //初值进栈
St[top].vm=m; St[top].vn=n; St[top].tag=1;
    while(top > -1){   //栈不空时循环
        if (St[top].tag==1)   //未计算出栈顶元素的vf值
        { 
            if (St[top].vm==0)      //(1)式
            {
St[top].vf=St[top].vn+1;
St[top].tag=0;
            } 
            else if (St[top].vn==0) //(2)式
            {
                top++;
St[top].vm=St[top-1].vm-1;
St[top].vn=1;
St[top].tag=1;
            }
            else                    //(3)式
            {
                top++;
St[top].vm=St[top-1].vm;
St[top].vn=St[top-1].vn-1;
St[top].tag=1;
            }
        }
        else if (St[top].tag==0)  //已计算出vf值
        {
            if (top>0 && St[top-1].vn==0) //(2)式
            {
St[top-1].vf=St[top].vf;
St[top-1].tag=0;
                top--;
            }
            else if (top > 0) //(3)式
            {
St[top-1].vm=St[top-1].vm-1;
St[top-1].vn=St[top].vf;
St[top-1].tag=1;
                top--;
            }
        }
        if(top==0 && St[top].tag==0) //栈中只有一个已求出vf的元素时退出循环
break;
    }
    return St[top].vf;

}




void main()
{
    int num1=0,num2=0,num3=0;
//  num1=akm1(0,1);
//  num2=akm1(1,2);
//  num3=akm1(3,3);

    num1=akm2(0,1);
    num2=akm2(1,2);
    num3=akm2(3,3);

    printf("akm2(0,1)= %d\n",num1);
    printf("akm2(1,2)= %d\n",num2);
    printf("akm2(3,3)= %d\n",num3);

}

效果如下：

图(1) Ackerman递归算法
图(2) Ackerman非递归算法