To show a friend (who confused recursion and primative recursion) that the ackermann function can be computed without recursion.

non-recursive-ackermann.py

# definition recursive ackermann
def A(m, n):
	if m == 0:
		return n + 1
	elif n == 0:
		return A(m - 1, 1)
	else:
		return A(m - 1, A(m, n - 1))

# non-recursive ackermann
# Explanation: Think rpn. Each iteration computes the result of A(m, n).
# Arguments are put onto the stack, each iteration pops two arguments pushes
# new arguments for recursion. Results are also placed onto the stack.
def B(m, n):
	stack = [m, n]
	while len(stack) > 1:
		n, m = stack.pop(), stack.pop()
		# compute ackermann
		if m == 0:
			#return n + 1
			stack.append(n + 1)
		elif n == 0:
			#return A(m - 1, 1)
			stack.append(m - 1)
			stack.append(1)
		else:
			#return A(m - 1, A(m, n - 1))
			stack.append(m - 1)
			stack.append(m)
			stack.append(n - 1)
	return stack.pop()

for m in range(4):
	for n in range(6):
		print("{:10}".format(A(m, n)), end="")
	print()

print()

for m in range(4):
	for n in range(6):
		print("{:10}".format(B(m, n)), end="")
	print()