问题描述
评测题目: 给出如下的递归函数，求ack(3,3)的值。
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));
}
编程方法
根据题目中的c语言程序改写成python如下：
cost = 0
def ack(m,n):
global cost
cost += 1
if m==0: return n+1
elif n==0: return ack(m-1,1)
else: return ack(m - 1, ack(m, n - 1))
print(ack(3,3))
print(cost)
运行得到结果为：
The answer is: 61
The number of iterations is: 2432
可知正确答案为61，计算机运行该程序时一共调用了ack()函数2432次。
数学方法
作为一道笔试题，想要迭代完成2432次计算是不可能的，因此这里讲解求ack(3,3)的数学思路。
-
讨论ack(1,0)和ack(2,0)，通过简单计算可得
-
讨论ack(1,n)，可得如下递归公式
-
讨论ack(2,n)，可得如下递归公式
-
讨论ack(3,n)，可得如下递归公式整理可得由等比数列公式可知又故
将n=3代入上式，可知正确答案为61。
