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

Question

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

所以我想我可以添加一个递归计数器，并在函数完全执行后快速暂停。我一直在获得预期的输出，直到它达到值(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内核崩溃。有上限吗？

我用的是最新的蟒蛇。

编辑

我尝试使用以下数据[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

原始实现的问题在于当output和rec都是数字时，如果返回output，rec将愉快地创建一个元组，当i=0时也是如此。但是，一旦i=1，j=0，函数就会调用(0,1，rec)上的Ackerman，它会返回一个元组，然后无法向其中添加整数rec，因此会出现错误消息。不过，我相信我已经实现了这个想法，几乎没有改变，只是我没有试图通过并返回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.recurisonlimit(我看了几次rec，至少我按照你的指示计算了它；此外，作为一次健全性检查，我切换了递增顺序和函数调用，得到了相同的结果)。

编辑：我添加了另一个参数来跟踪任何特定调用重复出现的深度。事实证明，这通常小于(最多比)"rec"。rec表示(实际上比)调用函数进行特定计算的次数，但并非所有这些都需要同时在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

Answer 2

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