2011年2月17日 星期四

[ 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 :
  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() :
  1. public static int fact(int n) {  
  2.     if(n==0return 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 : 

沒有留言:

張貼留言

[JS 文章收集] 用 Node.js 學 JavaScript 語言(1)簡介與安裝

Source From  Here   簡介   Node.js  是 Ryan Dahl 基於 Google 的 V8 引擎於 2009 年釋出的一個 JavaScript 開發平台,主要聚焦於 Web 程式的開發,通常用被來寫網站。但是,要開發網站就勢必要把「 HTML,...