I was playing with the recursive Ackermanns function. For certain values my prompt whould not show every calculated output 'cause Python whould exceed its recursive limit so fast that whould freeze the prompt before the "easy" parts whould catch up with it.
So I thought I could add a recursive counter and a quick pause after a full execution of the function. I was getting the anticipated outputs until it reached the values (1,0). After that I got a TypeError: can only concatenate tuple (not "int") to tuple
.
My code is as follows:
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)
Notice that removing all instances of rec
(my recurence counter), the program runs fine. (You can see all outputs for values i,j = 3
)
Can someone point out how to correct my code or propose a different method of finding how many times the Ackermann function has calls itself ?
Also, I've noticed that putting a limit of 5000 whould crash my python kernel very fast. Is there an upper limit ?
I use the latest Anaconda.
EDIT
I tried to implement the same function using a list as a parameter with the following data [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)
But this time I get a IndexError: list index out of range
because for some unknown reason my list gets emptied
OUTPUT:
[[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]]
[]