[ Data Structures with Java ] Section 14.3 : Recursion and the Runtime Stack

Preface : 
A program executes with a series of method calls that engage the runtime time. The execution process begins by having the calling statement setup anactivation record, which includes the list of runtime arguments, space for local variables declared in the method implementation, and a return address. The address is the location of the next instruction to execute after the method returns to the calling statement : 
 
Activation Record 

At the point of a method call, the runtime system pushes the activation record onto a system-supplied stack called runtime stack. Control then transfers to the statements in the method, where the data in the record is available for use in the method body. Upon executing from the method, the runtime system extracts the return address from the activation record and then pops the record from the stack. 
A recursive method makes repeated calls to itself by using a modified argument list for each call. The process pushes a chain of activation records onto the stack until the method identifies a stopping condition. The subsequent popping of the records gives the recursive solution. 
We use the factorial method fact() to illustrate the use of the activation records and the runtime stack. Assume the program makes a call to fact(3) from method main(). After fact(3) completes execution, program control returns to the assignment statement at address RetAddr1 in main(). The statement copies 6 (3!) into factValue : 

- Calling fact() in main :

view plaincopy to clipboardprint?

1. public static void main(String args[]) {  
2.     int factValue;  
3.     ...  
4.     factValue = fact(3)  // RetAddr1  
5.     System.out.println("Value fact(3) = "+factValue);  
6. }  

The recursive call with the method fact() returns to multiplication operation at address RetAddr2. The operation computes the product n*n(n-1)!, which becomes the return value for fact(n) : 

- Recursive call to fact() :

view plaincopy to clipboardprint?

1. public static int fact(int n) {  
2.     if(n==0) return 1; // Stopping condition  
3.     else return n*fact(n-1);   // RetAddr2  
4. }  

Let us view the runtime stack during execution of fact(3). An activation record has a field for the integer argument n and a field for the return address. The method doesn't define any local variables : 
 

The activation record for the call to fact(3) from method main() has an argument n=3 and the return address RetAddr1. Execution initiates a sequence of three recursive method calls with argument n=2,1 and 0 respectively. In each case, the activation record has address RetAddr2. The following figure illustrate how the stack grows with activation records for successive method calls : 
 

The stopping condition occurs in fact(0) and begins a sequence of return actions. Each step pops the activation record on the top of the stack and passes program control to the return address, which identifies the next instruction. The below figure illustrates the operation that describe the clearing of activation records from the runtime stack :