计算Ackerman函数在Python中被调用的次数

Question

我想写一个函数，这个函数能返回两个值。第一个值是阿克曼函数的输出，第二个值是这个函数被调用的次数。

我已经写好了阿克曼函数：

def ack(m,n):
    if m == 0:
        return n + 1
    elif m > 0 and n == 0:
        return ack(m - 1.0, 1.0)
    elif m > 0 and n > 0:
        return ack(m - 1.0, ack(m, n - 1.0))

我试着创建一个全局的计数器，在if和elif之前加上它，然后和结果一起返回：

global count
count +=1

if m == 0:
    return n+1, count

这样显然是不对的。这样做会在m等于0的时候每次都返回计数，而且返回的结果会是一个元组。

我该怎么做才能让它返回一个列表，比如调用ack(3,4)时应该返回125和调用ack(m,n)的次数。所以如果我调用ack(1.0,0.0)，它应该返回[2.0, 2]。我需要返回一个列表，因为我还需要用这个结果做一些计算。

我需要知道这个的原因是因为老师给了我们一个作业，而我完全卡住了。

Answer 1

只需要添加一个计数器，并在每次调用时增加它的值：

def ack(m,n):
    if m == 0:
        return n + 1, 1
    elif m > 0 and n == 0:
        res, count = ack(m - 1, 1)
        return res, count + 1
    elif m > 0 and n > 0:
        t, tc = ack(m, n - 1)
        res, rc = ack(m - 1, t)
        return res, tc + rc + 1

Answer 2

每次递归的时候就加1：

def ack(m,n):
    if m == 0:
        return (n + 1, 1)
    elif m > 0 and n == 0:
        a, cnt = ack(m - 1.0, 1.0)
        return a, cnt+1
    elif m > 0 and n > 0:
        a1, cnt1 = ack(m, n - 1.0)
        a2, cnt2 = ack(m - 1.0, a1)
        return a2, 1 + cnt1 + cnt2



>>> ack(3, 4)
    (125.0, 10307)
>>> ack(1, 0)
    (2.0, 2)