阿克曼函数
阿克曼函数（Ackerman）是非原始递归函数的例子；它需要两个自然数作为输入值，输出一个自然数。它的输出值增长速度非常高，仅是(4,3)的输出已大得不能准确计算。
Ackerman函数定义如下:
若m=0 返回n+1
若m>0且n=0 返回Ackerman(m-1,1)
若m>0且n>0 返回Ackerman(m-1,Ackerman(m,n-1))
以下是阿克曼函数的伪代码：
function ack(m, n)
begin
while m ≠ 0 do
begin
if n = 0 then n := 1
else
begin
n := ack(m, n-1);
m := m - 1;
end;
return( n+1);
end;
计算Ack(m,n)的非递归算法有
法一：
int Ackerman(int m.int n)
{
in akm[m][n];
int i,j;
memset(akm,o,sizeof(akm));
for(j=0;j<n;j++)
akm[0][j]=j+1;
for(i=1;i<m;i++)
{
akm[0]=akm[i-1][1];
for(j=1;j<n;j++)
{
akm[j]=akm[i-1][akm[j-1]];
}
}
return akm[m][n];
}
法二：
stack s;
int ack(int m,int n)
{
int top=0;
s[top].mval=m;
s[top].nval=n;
do
{
while(s[top].mval)
{
while(s[top].nval)
{
top++;
s[top].mval= s[top-1].mval;
s[top].nval= s[top-1].nval-1;
}
s[top].mval--;
s[top].nval=1;
}
if(top>0)
{
top--;
s[top].mval--;
s[top].nval= s[top+1].nval++;
}
}while(top!=0|| s[top].mval!=0);
ack= s[top].nval+1;
top--;
}