It is possible to compute recursive ackermann(m,n) function with args m>=4 and n>=1 in python without exceeding max recursion depth?

user_7885969 0
Viewed 1960

It is possible to compute total computable recursive function ackermann(m,n) with arguments m>=4 and n>=1 in python without exceeding max recursion depth?

def ackermann(m,n):

    if m == 0:
        return n+1
    if n == 0:
        return ackermann(m-1,1)
    else:
        return ackermann(m-1,ackermann(m,n-1))

ackermann(4,1)
ackermann recursion algorithm python
2 Answers

For this level of response, use dynamic programming: memoize the function. This means that you keep a table of previous results. If you find a result that's already been computed, then you return it from the table. Only when it's a new call, do you do the computation -- and in that case, most or all of the recursive calls will be in the table. For instance:

import sys
sys.setrecursionlimit(30000)

memo = {}

def ack(m, n):
    if not (m, n) in memo:
        result = (n + 1) if m == 0 else (
            ack(m-1, 1) if n == 0 else ack(m-1, ack(m, n-1)))
        memo[(m, n)] = result
    return memo[(m, n)]

print ack(3, 4)
print ack(4, 1)
print ack(4, 2)

You'll still have trouble with anything as large as ack(4, 2), due to memory use.

125
65533
Segmentation fault (core dumped)
user_47851850

Yes. One can use sys.setrecursionlimit and more mathematics to improve the algorithm. See The Rosetta Code task for Python code.

Note!

I just re-ran ack2:

%timeit a2 = ack2(4,2)
1000 loops, best of 3: 214 µs per loop

len(str(a2))
Out[9]: 19729

That is nearly twenty thousand digits in the answer.

user_105620
Related