I wrote code to calculate the Ackermann function and store the results, but at some random point it just stops (only for the lookup version though), the normal version just runs without stopping.
It can't be the recursion limit, maybe the dictionary is too big? It is not using too much memory, though.
Here is the code:
import time, sys
sys.setrecursionlimit(100000)
lookup = {}
def ackermann(m,n,look):
if (m,n) in lookup and look: #Checks if the pair is in the table
print("pair found")
return lookup[(m,n)]
else: #Regular ackermann
if m == 0:
print("Base found for {} {}".format(m,n))
return n+1
if n == 0:
print("Case 2: {} {}".format(m,n))
result = ackermann(m-1,1,look)
if look:
lookup[m,n] = result
return result
else:
print("Case 3: {} {}".format(m,n))
result = ackermann(m-1,ackermann(m,n-1,look),look)
if look:
lookup[m,n] = result
return result
def call_ack(m,n):
t1= time.time()
result1 = ackermann(m,n,True)
t2= time.time()
result2 = ackermann(m,n,False)
t3= time.time()
print("Result with lookup:",result1, "\nElapsed time:",t2-t1)
print("\nResult without lookup:",result2, "\nElapsed time:",t3- t2)
print("Difference: ", t3+t1-t2*2)
This is the final part of one of the outputs:
Case 3: 1 7947
Case 3: 1 7946
pair found
Base found for 0 7947
Base found for 0 7948
Case 3: 1 7949
Case 3: 1 7948
If I run it again:
Case 3: 2 4695
Case 3: 2 4694
Case 3: 2 4693
Case 3: 2 4692
Case 3: 2 4691
Case 3: 2 4690
Case 3: 2 4689
Case 3: 2 4688
Case 3: 2 4687
Case 3: 2 4686
Case 3: 2 4685
Case 3: 2 4684
Case 3: 2 4683
Case 3: 2 4682
Case 3: 2 4681
Case 3: 2 4680
Case 3: 2 4679
Without changing anything. Oh boy do I love inconsistent results! It is worth noting that for small values it runs just perfectly.
Edit: I just tried on this online python interpreter and it works just fine.
Edit 2: I've tried running it with another version of python (3.8.2 instead of 3.7) and it closes with a stack overflow error. The thing is that it is not using barely memory - at most 6.6 MB according with the task manager.