Ackermann function without recursive function calls, in Python

Python Help
1

Someone on reddit said that you could write Ackermanns function iteratively and gave a reference.(pdf). It turns out that the results all either replace recursive function calls with stacks, or with the use of arrays as stacks. Stacks are how recursive calls are made behind the scenes.

Having seen the papers examples, I took the idea of a stack and ran with it then plonked the result on Rosetta Code..

Here’s a copy of my initial version without optimisations on m. (The RC version has those optimisations and computes the practically computable values quickly).

from collections import deque


def ack_i(m, n):
    "Paddy3118's iterative"

    stack = deque([])
    stack.extend([m, n])

    while  len(stack) > 1:
        n, m = stack.pop(), stack.pop()

        if   m == 0:
            stack.append(n + 1)
        elif n == 0:
            stack.extend([m-1, 1])
        else:
            stack.extend([m-1, m, n-1])

    return stack[0]

"""
In [16]: %time ack_i(4, 1)
Wall time: 48min 45s
Out[16]: 65533

In [17]:
"""

.

1 Like