# ackermann.py

# info: https://en.wikipedia.org/wiki/Ackermann_function
# https://discuss.python.org/t/ackermann-function-without-recursive-function-calls-in-python/7026

import sys


def ack(m,n):
  if m == 0:
    return n+1
  elif n == 0:
    return ack(m-1, 1)
  else:
    return ack(m-1, ack(m, n-1))


def ackiter(m, n):
  stk = [m, n]
  while  len(stk) > 1:
    n, m = stk.pop(-1), stk.pop(-1)
    if  m == 0:
      stk.append(n + 1)
    elif n == 0:
      stk.extend([m-1, 1])
    else:
      stk.extend([m-1, m, n-1])
  return stk[0]


if __name__ == "__main__":
  # print("Recursion limit:", sys.getrecursionlimit())
  sys.setrecursionlimit(10**6)

  print("m,n:")
  for m in range(5):
    for n in range(5):
      print(f"({m},{n}): {ack(m,n):<3d}  ", end='', flush=True)
          # force output even though no newline
    print()
      # recursion crashes while calculating (4,1) == 2^2^2^2 - 3
      # iterative prints (4,1): 65533 but takes 20 mins