0

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]]
[]
0

2 Answers 2

1

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
3
  • Thank you, I didn't think putting a global variable for simlicity. Have you tried increasing the maximum recurence limit ? In my code putting 5000 whould immediately kill the Python core before any calculation.
    – Demis
    Commented Oct 18, 2017 at 17:18
  • So what is weird is even when I leave it at 3000, I get the above results with the 5213. 5000 did not break mine, but it also did not get me 4,1. I guess see if you get the same results. Commented Oct 18, 2017 at 23:00
  • The 5213, I believe, represents the number of times the function gets called in computing ack(3,4), but not all these need to be sitting on the Python interpreter stack at the same time. The recursion depth on that calculation is at most 127. Commented Oct 22, 2017 at 1:12
0

In your edited version of the code, you used a *arg in your def for ackerman and made it explicitly a list, and you get eleven output lists containing a four-element list in each until on the twelfth recursion you get an empty list. So, did the first eleven lists contain the expected elements according to the ackermann constraints? Also, on the twelfth recursion, you say the list was "emptied." I wonder for analytical purposes if it might make sense to say instead it wasn't filled in the first place. That is, not that something emptied it but that something didn't fill it as expected on the twelfth time through.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.