Ackermann 函数 $A(m, n)$ 的定义如下:
$$
A(m, n)=\left{\begin{array}{ll}
n+1 & \text { if } m=0 \
A(m-1,1) & \text { if } m>0 \text { and } n=0 \
A(m-1, A(m, n-1)) & \text { if } m>0 \text { and } n>0
\end{array}\right.
$$
查看维基百科的定义, 编写一个叫作ack的函数来计算 Ackermann 函数。使用你的函 数计算ack(3,4), 其结果应该为 125 。如果 $m$ 和 $n$ 的值较大时, 会发生什么?
拙见：
1
2
3
4
5
6
7
8
9
| def ack(m,n):
if m == 0:
return n+1
elif m > 0 and n == 0:
return ack(m-1,1)
elif m > 0 and n > 0:
return ack(m-1,ack(m,n-1))
ack(3,4)
|
似乎看上去平平无奇，把它的计算过程展示出来：
1
2
3
4
5
6
7
8
9
10
11
12
| def ack(m,n):
if m == 0:
print(n+1)
return n+1
elif m > 0 and n == 0:
print('ack(',m-1,',',1,')')
return ack(m-1,1)
elif m > 0 and n > 0:
print('ack(',m-1,',ack(',m,',',n-1,'))')
return ack(m-1,ack(m,n-1))
ack(3,4)
|
你可以自己动手运行一下看看，实际上进行了上万次递归。
作者的写法更简洁一些：
1
2
3
4
5
6
7
8
| def ackermann(m,n):
if m == 0:
return n+1
if n == 0:
return ackermann(m-1,1)
return ackermann(m-1, ackermann(m,n-1))
print(ackermann(3,4))
|
（补充说明一下，我的代码是在jupyter lab里运行的，所以不用使用print函数也能把结果显示出来。）