Ackerman函数

      并非一切递归函数都能用非递归方式定义，为了对递归函数的复杂性有更多的了解，双递归函数——Ackerman函数，当一个函数以及它的一个变量是由函数自身定义时，称这个函数是双递归函数，Ackerman函数A（n,m）有两个独立的整变量m>=0和n>=0，其定义如下：

          A(1,0)=2

          A(0,m)=1                                   m>=0

          A(n,0)=n+2                                n>=2

          A(n,m)=A(A(n-1,m),m-1)            n,m>=1

      A (n,m)的自变量m的每一个值都定义了一个单变量函数,例如,递归式的第三式表示m=0定义了函数"加2"。m=1时，由于A(1,1)=A(A(0,1),0)=A(1,0)=2以及A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2(n>1),因此A(n,1)=2n(n>=1),即A(n,1)是函数"乘2"。

      类似地可以推出,A(n,3)=2∧2...2,其中2的层数为n。

      A(n,4)的增长速度非常快，以至于没有适当的数学式子来表示这一函数。

      单变量的Ackerman函数A(n)定义为：A(n)=A(n,n)。其拟逆函数a(n)在算法复杂性分析中常遇到。它定义为：a(n)=min{k|A(k)>=n}。即a(n)是使n<=A(k)成立的最小的k值。

       例如，由A(0)=1,A(1)=2,A(2)=4和A(3)=16推知，a(1)=0,a(2)=1,a(3)=a(4)=2和a(5)=...=a(16)=3。可以看出a(n)的增长速度非常慢。

       A(4)=2∧2...2,其中2的层次为65536，这个数非常大，无法用通常德方式来表达它。如果要写出这个数将需要log(A(4))位，即2∧2...2(65535层2的方幂)位。所以,对于通常所见到的正常数n,有a(n)<=4。但在理论上a(n)没有上界，随着n的增加,它以难以想象的慢速度趋向正无穷大。