阿克曼函数（Ackermann）是非
原始递归函数的例子。它需要两个自然数作为输入值，输出一个自然数。它的输出值增长速度非常快，仅是对于(4,3)的输出已大得不能准确计算。
历史
1920年代后期，数学家
大卫·希尔伯特的学生Gabriel Sudan和威廉·阿克曼，当时正研究计算的基础。Sudan发明了一个递归却非原始递归的Sudan函数。1928年，阿克曼又独立想出了另一个递归却非原始递归的函数。[1]
他最初的念头是一个三个变量的函数A(m,n,p)，使用
康威链式箭号表示法是m→n→p。阿克曼证明了它是
递归函数。希尔伯特在On the Infinite猜想这个函数不是
原始递归函数。阿克曼在On Hilbert's Construction of the Real Numbers证明了这点。
后来Rózsa Péter和拉斐尔·米切尔·罗宾逊定义了一个类似的函数，但只用两个变量。
定义
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函数）α(x)定义为最大的整数m使得Ackermann(m,m)≤x。从上面的讨论中可以看到，因为Ackermann函数的增长很快，所以其反函数α(x)的增长是非常慢的，对所有在实际问题中有意义的x，α(x)≤4，所以在算法
时间复杂度分析等问题中，可以把α(x)看成常数。
α(x)出现在使用了按秩合并和路径压缩的
并查集算法的
时间复杂度中。
计算代码
递归算法
int ack(int m,int n){
while(m!=0){
if( n==0) n=1;
else{
n=ack(m, n-1);}
m--;
}
return n+1;
}
非递归算法一
int Ackermann(int m,int n)
{
int akm[m][n];
int i,j;
memset(akm,o,sizeof(akm));
for(j=0;j
akm[0][j]=j+1;
for(i=1;i
{
akm[0]=akm[i-1][1];
for(j=1;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+1;
}
}while(top!=0||s[top].mval!=0);
ack=s[top].nval+1;
top--;
}