Simulating recursion using stack (Eliminating recursion)

If a programming language does not support recursion or one needs a non-recursive code, then a recursive code can be translated to a non-recursive one. Once a recursive function is written and is verified for its correctness, one can remove recursion for efficiency.

Eliminating recursion can be done using the following rules:

1. At the beginning of the recursive function, a code is inserted to create an empty stack. This stack is to be used to hold the values of parameters, the local variables, the function value, and the return address for each recursive call.

2. The jump label is attached to the first executable statement (say label_1). Now, replace each recursive call by a set of instructions that perform the following:

            (a) Push the values of all parameters and local variables on the stack.

(b) Create the ith new label, label_i and store i in the stack. The value i of this label will be used to compute the return address.

(c) Evaluate the arguments of this call, which may be part of the expression. Assign these values to the appropriate formal parameters.

(d) Insert an unconditional branch to the beginning of the function.

(e) Attach the label created in step 2(b) to the statement immediately following the

unconditional branch.

3. Once all the recursive calls have been eliminated, replace all the return statements using the following steps:

(a) If the stack is empty, then execute a normal return.

(b) Otherwise, take the current value of all the output parameters (explicitly or implicitly understood to be of type output or input) and assign these values to the corresponding variables that are on top of the stack.

(c) Now, insert a code that removes the index of the return address from the stack if any has been placed there. Assign this address to some unused variable.

(d) Remove the values of all local variables and parameters from the stack and assign them to their corresponding variables.

(e) If this is a function, insert instructions to evaluate the expression immediately following return() and store the result on the top of the stack.

(f) Use the index of the label of the return address to execute a branch to that label.

If all these rules are followed carefully, one can convert recursion to an iterative code.