如何计算 Python 中函数的递归调用？

Question

我正在玩递归 Ackermanns 函数。对于某些值，我的提示不会显示每个计算的输出，因为 Python 会很快超过其递归限制，以至于会在 "easy" 部分赶上它之前冻结提示。

所以我想我可以在函数完全执行后添加一个递归计数器和一个快速暂停。在达到值 (1,0) 之前，我一直在获得预期的输出。之后我得到了一个TypeError: can only concatenate tuple (not "int") to tuple。

我的代码如下：

import time
import sys
sys.setrecursionlimit(3000)

def ackermann(i,j,rec):
    output = None
    if i==0:
        output = j+1
    elif j==0:
        output = ackermann(i-1,1,rec)
        rec=rec+1
    else:
        output = ackermann(i-1,ackermann(i,j-1,rec),rec)
        rec=rec+1
    return output,rec

rec=0
for i in range(5):
    for j in range(5):
        print("(",i,",",j,")= ",ackermann(i,j,rec))
        time.sleep(2)

请注意，删除 rec（我的递归计数器）的所有实例后，程序运行良好。（您可以看到值 i,j = 3 的所有输出）

有人可以指出如何更正我的代码或提出一种不同的方法来查找 Ackermann 函数调用自身的次数吗？

此外，我注意到设置 5000 的限制会使我的 python 内核崩溃得非常快。有上限吗？

我用的是最新的Anaconda

编辑

我尝试使用列表作为参数实现相同的功能，数据如下[i,j,output,#recursion]

import time
import sys
sys.setrecursionlimit(3000)

def ackermann(*rec):
    rec=list(rec)
    print(rec) # see the data as they initialize the function
    if rec[0][0]==0:
        rec[0][1]=rec[0][1]+1
        rec[0][2] = rec[0][1]+1
    elif rec[0][1]==0:
        rec[0][0]=rec[0][0]-1
        rec[0][1]=1
        rec = ackermann()
        rec[0][3]=rec[0][3]+1
    else:
        rec[0][0]=rec[0][0]-1
        rec[0][1] = ackermann()
        rec = ackermann()
        rec[0][3]=rec[0][3]+1
    return rec

for i in range(5):
    for j in range(5):
        rec=[i,j,0,0]
        print(ackermann(rec))
        time.sleep(1)

但是这次我收到 IndexError: list index out of range因为某些未知原因我的列表被清空了

输出：

[[0, 0, 0, 0]]
[[0, 1, 2, 0]]
[[0, 1, 0, 0]]
[[0, 2, 3, 0]]
[[0, 2, 0, 0]]
[[0, 3, 4, 0]]
[[0, 3, 0, 0]]
[[0, 4, 5, 0]]
[[0, 4, 0, 0]]
[[0, 5, 6, 0]]
[[1, 0, 0, 0]]
[]

Answer 1

在您编辑的代码版本中，您在 def 中为 ackerman 使用了一个 *arg 并将其显式设为一个列表，并且您得到 11 个输出列表，每个列表包含一个四元素列表，直到第十二次递归得到一个空列表。那么，根据 ackermann 约束，前 11 个列表是否包含预期的元素？另外，在第十二次递归中，你说列表是 "emptied." 我想知道出于分析目的，说它一开始就没有被填满是否有意义。也就是说，不是有什么东西把它清空了，而是有什么东西在第十二次通过时没有像预期的那样填满它。

Answer 2

原始实现的问题在于 return 输出，rec 当 output 和 rec 都是数字时，将愉快地创建一个元组，当 i=0 时为真。但是一旦你到达 i=1, j=0 函数在 (0,1,rec) 上调用 Ackerman，return 是一个元组，然后它不能添加整数 rec，因此错误消息。我相信我已经使用了这个想法，但几乎没有改变，除了我没有尝试通过和 return rec，而是让它成为全球性的（丑陋的，我知道）。我还重新格式化了输出，以便更好地阅读。因此：

import time
import sys
sys.setrecursionlimit(3000)
def ackermann(i,j):
    global rec
    output = None
    if i==0:
        output = j+1
    elif j==0:
        output = ackermann(i-1,1)
        rec=rec+1
    else:
        output = ackermann(i-1,ackermann(i,j-1))
        rec=rec+1
    return output


for i in range(5):
    for j in range(5):
        rec = 0
        print
        print("ack("+str(i)+","+str(j)+") = "+str(ackermann(i,j)))
        print("rec = "+str(rec))
        print
        time.sleep(1)

并且在出错之前的输出是，

ack(0,0) = 1
rec = 0


ack(0,1) = 2
rec = 0


ack(0,2) = 3
rec = 0


ack(0,3) = 4
rec = 0


ack(0,4) = 5
rec = 0


ack(1,0) = 2
rec = 1


ack(1,1) = 3
rec = 2


ack(1,2) = 4
rec = 3


ack(1,3) = 5
rec = 4


ack(1,4) = 6
rec = 5


ack(2,0) = 3
rec = 3


ack(2,1) = 5
rec = 8


ack(2,2) = 7
rec = 15


ack(2,3) = 9
rec = 24


ack(2,4) = 11
rec = 35


ack(3,0) = 5
rec = 9


ack(3,1) = 13
rec = 58


ack(3,2) = 29
rec = 283


ack(3,3) = 61
rec = 1244


ack(3,4) = 125
rec = 5213


ack(4,0) = 13
rec = 59

在我看来，只有一两个其他值（我相信它会在 4,2 上窒息，无论如何，所以你需要先获得 5、0）你可能希望摆脱这个方式，无论你修补多少。

我对 rec 似乎超过递归限制感到有点困扰，但我认为 Python 一定是在以某种方式解释，所以它变得比人们想象的更深，或者我不知道没有完全理解 sys.recursionlimit（我看了几次 rec ，至少我按照你的指导计算了它；另外，作为完整性检查，我切换了递增它的顺序和函数调用并得到了相同的结果）。

编辑：我添加了另一个参数来跟踪任何特定调用的递归深度。事实证明通常小于（并且最多多于） "rec." rec 表示（实际上小于 1）函数被调用以进行特定计算的次数，但并非所有这些都需要打开Python 解释器同时堆栈。

修改后的代码：

import time
import sys
sys.setrecursionlimit(3000)
def ackermann(i,j,d):
    global rec
    global maxDepth
    if ( d  > maxDepth ) : maxDepth = d
    output = None
    if i==0:
        output = j+1
    elif j==0:
        rec=rec+1
        output = ackermann(i-1,1, d+1)
    else:
        rec=rec+1
        output = ackermann(i-1,ackermann(i,j-1, d+1),d+1)
    return output


for i in range(5):
    for j in range(5):
        rec = 0
        maxDepth=0
        print
        print("ack("+str(i)+","+str(j)+") = "+str(ackermann(i,j,1)))
        print("rec = "+str(rec))
        print("maxDepth = "+str(maxDepth))
        print
        time.sleep(1)

修改后的输出（在它放弃之前）

ack(0,0) = 1
rec = 0
maxDepth = 1


ack(0,1) = 2
rec = 0
maxDepth = 1


ack(0,2) = 3
rec = 0
maxDepth = 1


ack(0,3) = 4
rec = 0
maxDepth = 1


ack(0,4) = 5
rec = 0
maxDepth = 1


ack(1,0) = 2
rec = 1
maxDepth = 2


ack(1,1) = 3
rec = 2
maxDepth = 3


ack(1,2) = 4
rec = 3
maxDepth = 4


ack(1,3) = 5
rec = 4
maxDepth = 5


ack(1,4) = 6
rec = 5
maxDepth = 6


ack(2,0) = 3
rec = 3
maxDepth = 4


ack(2,1) = 5
rec = 8
maxDepth = 6


ack(2,2) = 7
rec = 15
maxDepth = 8


ack(2,3) = 9
rec = 24
maxDepth = 10


ack(2,4) = 11
rec = 35
maxDepth = 12


ack(3,0) = 5
rec = 9
maxDepth = 7


ack(3,1) = 13
rec = 58
maxDepth = 15


ack(3,2) = 29
rec = 283
maxDepth = 31


ack(3,3) = 61
rec = 1244
maxDepth = 63


ack(3,4) = 125
rec = 5213
maxDepth = 127


ack(4,0) = 13
rec = 59
maxDepth = 16

如何计算 Python 中函数的递归调用？

How can I count the recursive calls of a function in Python?

recursion

python-3.x

ackermann