How to convert Hyperoperation from recursion to iteration?

Question

I’ve been exploring the hyperoperation sequence, which is typically defined recursively. enter image description here

According to the same source, hyperoperations can be expressed using iteration, but the examples still appear to rely on recursion at their core. The recursive definition of hyperoperations uses the result of the previous level to compute the next result, which seems inherently recursive. enter image description here

But Wikipedia also said:

Every recursive function can be transformed into an iterative function by replacing recursive calls with iterative control constructs and simulating the call stack with a stack explicitly managed by the program.

However, despite reading the section on "Iteration of Hyperoperation" on Wikipedia, I’m still unclear on how to completely convert these recursive definitions into an iterative form. So my question is: Can the recursive nature of hyperoperations be entirely removed?

If it can be transformed into an iterative version, how can this be achieved without relying on recursion? Any clarification or examples of how to make hyperoperations purely iterative would be greatly appreciated such as a pseudocode that purely using while and for syntax only.

Answer 1

All recursive algorithms can be translated to iterative commands. There are no recursive operations in the assembler/bytecode that represents your program after compilation. In principle, you could read the resulting assembler and translate it using for's and while's to replace assembly jumps.

Anyway, for your particular question, the Wikipedia page already provides an iterative algorithm for hyperoperations using reduction rules and a stack. Here's a non-recursive solution in Python:

def hyper(n, a, b):
 stack = [n, a, b]
 while len(stack) > 1:
 *stack, n, a, b = stack
 if n == 0:
 stack.append(b+1)
 elif b == 0:
 if n == 1: stack.append(a)
 elif n == 2: stack.append(0)
 else: stack.append(1)
 else:
 stack.extend([n-1, a, n, a, b-1])
 return stack[0]
assert hyper(2, 2, 5) == 10 # 2*5
assert hyper(3, 2, 5) == 32 # 2**5
assert hyper(4, 2, 3) == 16 # 2**2**2
assert hyper(4, 3, 2) == 27 # 3**3