Recursion

A procedure contains either a call statement to itself or a call statement to a second procedure that may eventually result in a call statement back to the original procedure. Then suck kind of problems known as recursive procedure. For Example : the factorial can be solved using a recursive procedure.

Recursion may be useful in developing algorithm for specific problems. The stack is a perfect data structure to implement recursive procedures. A recursive problem is divided into subprograms. A subprograms can contain both parameters and local variables. The parameters are the variables which receive values from objects in the calling programs, called arguments and which transmit values back to the calling program.

The subprogram, besides the parameters and local variables, also keeps track of return address in the calling program. This return address is essential, since control must be transferred back to its proper place in the calling program. Once the subprogram is finished executing and control is transferred back to its calling programs, the values of local variables and return address are no longer needed.

Suppose the subprogram is a recursive program. Then each level of execution of the subprogram may contain different values for parameters and local variables and for the return address. Now, if the recursive subprogram call itself, then these current values must be saved, since they will be used again when program is reactivated.

The translation of recursive procedure into a non-recursive procedure using stack is as follows:

1. Declare a stack that will hold the active records consisting of all local variables, parameters called by value and labels to specify where the function is recursively called if it calls itself from several places.
2. The non-recursive function for a recursive function starts with an initialization block which initializes the stack to NULL. The stack and the stack top pointer are defined as global variables.
3. To enable each recursive call to start at the beginning of the original function its first executable statement after the stack initialization block is associated with a label.
4. Now, inside the function the following steps should be considered, where it is recursively called, while working with stack.
5. Push all local variables and parameters called by value into the stack.
6. Push an integer ‘i’ into the stack if this is the i^th place from where the function is called recursively.
7. Set the formal parameters called by value to the values given in the new call to the recursive function.
8. Replace the call to recursive function with a goto statement which is the first statement after the stack initialization block. A label is associated to this step 2.
9. Make a new statement label L(if this is the i^th place from where the function is called recursively) and attach the label to the first statement after the call to the same function so that a return can be made to this label.
10. At the end of recursive function, the following steps should be performed.
11. If the stack is empty, then the recursion has finished; make a normal return.
12. Otherwise, pop the stack to restore the values of all local variables and parameters called by value.
13. Pop the integer ‘i’ from the stack and use this to go to the statement labeled L.