Ackerman函数

Ackerman函数在许多讲解递归的书中都提到，但似乎又对解题没有太大的意义，暂时不知道了。不过这个东西，是一个数学知识点，暂时收藏于此吧。

查了一下维基百科和百度百科，表面上两个定义不一样，仔细推敲其实是一样的。（维基百科里面A（m，n）和百度百科里面A（n，m）当中的参数n、m代表含义是一样的，只是它们两个递归函数的参数的顺序写的不一样而已。）

先看Fibonacci数列

Fibonacci数列是一个非常重要，应用非常广的知识点，其递归定义如下：

（百度百科：http://baike.baidu.com/link?url=hSbCp3OLCl79y1H_fDWugAniyMFuEK7IlB2KB--g2oLAMkcWvv_3wkJRjClkq2cg）

递推公式

斐波那契数列：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

如果设F(n）为该数列的第n项（n∈N*），那么这句话可以写成如下形式：

显然这是一个线性递推数列。

通项公式

下面看看Ackerman函数：

Fibonacci数列可以写出通项公式，就是用非递归的方式去下定义。但并非一切的递归函数都能用非递归方式去定义。下面讲一个双递归函数——Ackerman函数，它的复杂性就比Fibonacci数列递归公式要复杂多了。

百度百科：Ackerman函数  （其实下面百度百科关于Ackerman函数的描述大体是抄自王晓东的《算法设计与分析（第2版）》清华大学出版社第2章递归与分治策略例题2.3 。）

当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数.当两个连续函数都趋于无穷时，我们常用洛必达法则来比较它们趋向无穷的快慢。函数的阶越高，它趋向无穷的速度就越快。在定义在正整数域上的函数中，n!趋向于正无穷的速度非常快，所以在算法设计中如果出现这样的时间复杂度就太糟糕了。logn趋向无穷的速度则非常慢。

以此类推，，其中2的层数为n。

A(n,4)的增长速度已经变得难以想象的快，以至于不能写出一个通项公式来表示这一函数。

维基百科：Ackerman函数的描述

定义如下：

乍一看，这个定义和上面百度百科给的定义不太一样。仔细分析，其实它们两个A（）函数当中的m、n含义没变，只是参数当中顺序刚好相反而已。

下面是网友的代码：（来源：http://blog.csdn.net/gpengtao/article/details/7438587）

int ack(int m,int n)
{
    if(m == 0)
        return n+1;
    else if(n == 0)
        return ack(m-1,1);
    else
        return ack(m-1,ack(m,n-1));
}