阿克曼函数（Ackermann）是非原始递归函数的例子。它需要两个自然数作为输入值，输出一个自然数。它的输出值增长速度非常高，仅是对于(4,3)的输出已大得不能准确计算。

定义

意义

反Ackermann函数

计算代码(递归算法 非递归算法一 非递归算法二)

定义

Ackermann函数定义如下：若m=0，返回n+1。

若m>0且n=0，返回Ackermann(m-1,1)。

若m>0且n>0，返回Ackermann(m-1,Ackermann(m,n-1))。

意义

从Ackermann函数的定义中可以看出，Ackermann函数可以看成关于n的一个函数序列，其中第0个函数返回n+1，而第m个函数则是将第m-1个函数对1迭代n+1遍。对较小的m，该函数为：

Ackermann(0,n)=n+1

Ackermann(1,n)=n+2

Ackermann(2,n)=2*n+3

Ackermann(3,n)=2^(n+3)-3

Ackermann(4,n)=2^2^2^……^2-3，乘幂中共有n+3个2。

当m≥4，Ackermann函数的增长快得惊人。Ackermann(4,0)=13，Ackermann(4,1)=65533，Ackermann(4,2)=2^65536-3有19729位，而Ackermann(4,3)则即使是位数也不易估计。Ackermann(5,0)=65533，Ackermann(5,1)=Ackermann(4,65533)……

反Ackermann函数

单变量反Ackermann函数（简称反Ackermann函数）α(x)定义为最大的整数m使得Ackermann(m,m)≤x。从上面的讨论中可以看到，因为Ackermann函数的增长很快，所以其反函数α(x)的增长是非常慢的，对所有在实际问题中有意义的x，α(x)≤4，所以在算法时间复杂度分析等问题中，可以把α(x)看成常数。

α(x)出现在使用了按秩合并和路径压缩的并查集算法的时间复杂度中。

计算代码

递归算法

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;

非递归算法一

int Ackermann(int m,int n)

{

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

}