Question

递归函数问题

仔细阅读以下一段递归的函数定义：
in tack(int m,int n)
{
if(m==0)
{
return
n+1;
}
Else if(n==0)
{
return
ack(m-1,1);
}
else
{
retrun
ack(m-1,ack(m,n-1));
}
}
请问ack(3,3)的返回值是( )。

还有请问高手ack（）是什么算法，谢谢！

Answer 1

解题步骤：

1,ack(1,n)=ack(0,ack(1,n-1))+1=ack(1,n-1)+1;

由递推式得：ack(1,n)=n+1;

2，ack(2,n)=ack(1,ack(2,n-1))=ack(2,n-1)+2;
//递推式

由递推式得：ack(2,n)=2n+3;

3,ack(3,n)=ack(2,ack(3,n-1))=2*ack(3,n-1)+3; //递推式

即：ack(3,n)+3=2(ack(3,n-1)+3)

得: ack(3,n)+3=(ack(3,1)+3) * 2^(n-1);

又ack(3,1)=2ack(3,0)+3

ack(3,0)=a(2,1)=5

所以ack(3,1)=13;

所以 ack(3,n)=2^(n+3) -
3;

所以：ack(3,3)=61;

PS：
这个是著名的Ackerman（阿克曼）函数，典型的非原始递归的递归函数，m<=3的时候像我上面的递推和计算很简单，但是一旦再大就会很麻烦，甚至计算机会彻底无法计算。
可以参考wiki资料了解相关内容：
http://zh.wikipedia.org/zh-cn/%E9%98%BF%E5%85%8B%E6%9B%BC%E5%87%BD%E6%95%B8