阿克曼函数

阿克曼函数（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--;

}