Think Python Exercise 6.2 阿克曼函数

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函数也能把结果显示出来。)