# 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))
IyBodHRwOi8vc3RhY2tvdmVyZmxvdy5jb20vcXVlc3Rpb25zLzk4MzE2NjYvaG93LWNhbi15b3UtZW11bGF0ZS1yZWN1cnNpb24td2l0aC1hLXN0YWNrCgpkZWYgYWNrKG0sIG4pOgogICAgYXNzZXJ0IG0gPj0gMCBhbmQgbiA+PSAwCiAgICBpZiBtID09IDA6IHJldHVybiBuICsgMQogICAgaWYgbiA9PSAwOiByZXR1cm4gYWNrKG0gLSAxLCAxKQogICAgcmV0dXJuIGFjayhtIC0gMSwgYWNrKG0sIG4gLSAxKSkKCmRlZiBhY2tfaXRlcihtLCBuKToKICAgIHN0YWNrID0gW10KICAgIHB1c2ggPSBzdGFjay5hcHBlbmQKICAgIHBvcCA9IHN0YWNrLnBvcAogICAgUkVUVVJOX1ZBTFVFLCBDQUxMX0ZVTkNUSU9OLCBORVNURUQgPSAtMSwgLTIsIC0zCgogICAgcHVzaChtKSAjIHB1c2ggZnVuY3Rpb24gYXJndW1lbnRzCiAgICBwdXNoKG4pCiAgICBwdXNoKENBTExfRlVOQ1RJT04pICMgcHVzaCBhZGRyZXNzCiAgICB3aGlsZSBzdGFjazogIyBub3QgZW1wdHkKICAgICAgICBhZGRyZXNzID0gcG9wKCkKICAgICAgICBpZiBhZGRyZXNzIGlzIENBTExfRlVOQ1RJT046CiAgICAgICAgICAgIG4gPSBwb3AoKSAgIyBwb3AgZnVuY3Rpb24gYXJndW1lbnRzCiAgICAgICAgICAgIG0gPSBwb3AoKQogICAgICAgICAgICBpZiBtID09IDA6ICMgcmV0dXJuIG4gKyAxCiAgICAgICAgICAgICAgICBwdXNoKG4rMSkgIyBwdXNoIHJldHVybmVkIHZhbHVlCiAgICAgICAgICAgICAgICBwdXNoKFJFVFVSTl9WQUxVRSkKICAgICAgICAgICAgZWxpZiBuID09IDA6ICMgcmV0dXJuIGFjayhtIC0gMSwgMSkKICAgICAgICAgICAgICAgIHB1c2gobS0xKQogICAgICAgICAgICAgICAgcHVzaCgxKQogICAgICAgICAgICAgICAgcHVzaChDQUxMX0ZVTkNUSU9OKQogICAgICAgICAgICBlbHNlOiAjIGJlZ2luOiByZXR1cm4gYWNrKG0gLSAxLCBhY2sobSwgbiAtIDEpKQogICAgICAgICAgICAgICAgcHVzaChtLTEpICMgc2F2ZSBsb2NhbCB2YWx1ZQogICAgICAgICAgICAgICAgcHVzaChORVNURUQpICMgc2F2ZSBhZGRyZXNzIHRvIHJldHVybgogICAgICAgICAgICAgICAgcHVzaChtKQogICAgICAgICAgICAgICAgcHVzaChuLTEpCiAgICAgICAgICAgICAgICBwdXNoKENBTExfRlVOQ1RJT04pCiAgICAgICAgZWxpZiBhZGRyZXNzIGlzIE5FU1RFRDogIyBlbmQ6IHJldHVybiBhY2sobSAtIDEsIGFjayhtLCBuIC0gMSkpCiAgICAgICAgICAgICMgb2xkIChtIC0gMSkgaXMgYWxyZWFkeSBvbiB0aGUgc3RhY2sKICAgICAgICAgICAgcHVzaCh2YWx1ZSkgIyB1c2UgcmV0dXJuZWQgdmFsdWUgZnJvbSB0aGUgbW9zdCByZWNlbnQgY2FsbAogICAgICAgICAgICBwdXNoKENBTExfRlVOQ1RJT04pCiAgICAgICAgZWxpZiBhZGRyZXNzIGlzIFJFVFVSTl9WQUxVRToKICAgICAgICAgICAgdmFsdWUgPSBwb3AoKSAjIHBvcCByZXR1cm5lZCB2YWx1ZQogICAgICAgIGVsc2U6CiAgICAgICAgICAgIGFzc2VydCAwLCAoYWRkcmVzcywgc3RhY2spCiAgICByZXR1cm4gdmFsdWUKCnByaW50KGFjaygyLCA0KSkKcHJpbnQoYWNrX2l0ZXIoMiwgNCkpCmFzc2VydCBhbGwoYWNrKG0sIG4pID09IGFja19pdGVyKG0sIG4pIGZvciBtIGluIHJhbmdlKDQpIGZvciBuIGluIHJhbmdlKDYpKQpwcmludChhY2tfaXRlcigzLCA0KSkK