4

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)
ᴀʀᴍᴀɴ
  • 4,443
  • 8
  • 37
  • 57
madmax80
  • 171
  • 1
  • 14
  • 7
    You know that the ackerman was intentionally defined to show something that increases that largely that it could not be defined by primitive recursive functions? – Willem Van Onsem Oct 05 '17 at 18:48
  • 3
    Python is not good for recursion. There is no tail-call elimination, and thus, it is always prone to stack-overflow. You can increase the max-recursion depth, but that's there to *prevent* the stack-overflow... – juanpa.arrivillaga Oct 05 '17 at 18:49
  • *ackermann(4, 2)* has almost twenty-thousand decimal digits - and so has the nesting depth taking the (above) definition literally. – greybeard Oct 05 '17 at 19:08

2 Answers2

3

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)
Prune
  • 76,765
  • 14
  • 60
  • 81
2

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.

Paddy3118
  • 4,704
  • 27
  • 38
  • Note that there are *two* versions of **ack2** on the Rosetta page. My answer is derived from the first; I believe you ran the second, "From the Mathematica ack3 example." I tried that one, and it has no trouble with ack(4,2). However, ack(5, 1) still gets a stack overflow, and ack(4, 3) runs a loooong time (as expected). I killed the job after 15 minutes. – Prune Oct 06 '17 at 15:56