# http://stackoverflow.com/questions/9831666/how-can-you-emulate-recursion-with-a-stack

def ack(m, n):
    assert m >= 0 and n >= 0
    if m == 0: return n + 1
    if n == 0: return ack(m - 1, 1)
    return ack(m - 1, ack(m, n - 1))

def ack_iter(m, n):
    stack = []
    push = stack.append
    pop = stack.pop
    RETURN_VALUE, CALL_FUNCTION, NESTED = -1, -2, -3

    push(m) # push function arguments
    push(n)
    push(CALL_FUNCTION) # push address
    while stack: # not empty
        address = pop()
        if address is CALL_FUNCTION:
            n = pop()  # pop function arguments
            m = pop()
            if m == 0: # return n + 1
                push(n+1) # push returned value
                push(RETURN_VALUE)
            elif n == 0: # return ack(m - 1, 1)
                push(m-1)
                push(1)
                push(CALL_FUNCTION)
            else: # begin: return ack(m - 1, ack(m, n - 1))
                push(m-1) # save local value
                push(NESTED) # save address to return
                push(m)
                push(n-1)
                push(CALL_FUNCTION)
        elif address is NESTED: # end: return ack(m - 1, ack(m, n - 1))
            # old (m - 1) is already on the stack
            push(value) # use returned value from the most recent call
            push(CALL_FUNCTION)
        elif address is RETURN_VALUE:
            value = pop() # pop returned value
        else:
            assert 0, (address, stack)
    return value

print(ack(2, 4))
print(ack_iter(2, 4))
assert all(ack(m, n) == ack_iter(m, n) for m in range(4) for n in range(6))
print(ack_iter(3, 4))