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 rangebecause 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]]
[]
The problem with the original implementation is that return output, rec will happily create a tuple when output and rec are both numbers, which is true whenever i=0. But once you get to i=1, j=0 the function calls Ackerman on (0,1,rec), which returns a tuple, to which it then cannot add the integer rec, hence the error message. I believe I have worked with that idea, though, almost unchanged, except rather than trying to pass and return rec, I made it global (ugly, I know). I also reformatted the output so I could read it better. Thus:
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)
and the output, before erroring out, is,
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
It seems to me there are only one or two other values (it will choke on 4,2 I believe, no matter what, so you would need to get 5, 0 first) you could hope to get out this way, no matter how much you tinker.
I am a little troubled that rec appears to exceed the recursion limit, but I think Python must be interpreting along the way somehow, so that it gets deeper than one might think, or that I don't fully understand sys.recursionlimit (I looked at rec a few times, and at the very least I followed your lead on calculating it; also, as a sanity check I switched the order of incrementing it and the function call and got the same results).
EDIT: I added another parameter to track how deeply any particular call ever recurses. That turns out to be typically less than (and at most one more than) "rec." rec represents (actually 1 less than) how many times the function is called to make the particular calculation, but not all of these need be on the Python interpreter stack simultaneously.
Revised code:
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)
revised output (before it gives up)
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