已知Ackerman函数的定义如下：
$$akm(m,n)=\{\begin{array}{ll}n+1,& \text{m = 0}\\ akm(m-1,1),& m\ne 0,n=0\\ akm(m-1,akm(m,n-1)),& m\ne 0,n\ne 0\end{array}$$

请设计对应的递归算法和非递归算法。

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);

}

    效果如下：