In Chapter 6, the stack data structure was introduced in the context of understanding how Java performs method calls. We discussed both the method call stack (also known as the program execution stack) and activation records. In this section, we will use these concepts to demonstrate how the program execution stack handles recursive method calls.
Let us begin by returning to the Fibonacci examplespecifically, calling method fibonacci with the value 3, as in Fig. 15.7. To more easily demonstrate in what order the activation records for the method calls are placed on the stack, we have lettered the method calls, as shown in Fig. 15.8.
Figure 15.8. Method calls made within the call fibonacci ( 3 ).
When the first method call (A) is made, an activation record is pushed onto the program execution stack which contains the value of the local variable number (3, in this case). The program execution stack, including the activation record for method call A, is illustrated in part a of Fig. 15.9. [Note: In an actual computer, the program execution stack and its activation records would be more complex than in Fig. 15.9, containing such information as where the method call is to return to when it has completed execution. We use a simplified stack to demonstrate how the program execution stack works.]
Figure 15.9. Method calls on the program execution stack.
(This item is displayed on page 754 in the print version)
Within method call A, method calls B and E are made. The original method call has not yet completed, so its activation record remains on the stack. The first method call to be made from within A is method call B, so the activation record for method call B is pushed onto the stack on top of the activation record for method call A. Method call B must execute and complete before method call E is made. Within method call B, method calls C and D will be made. Method call C is made first, and its activation record is pushed onto the stack (part b of Fig. 15.9). Method call B has not yet finished, and its activation record is still on the method call stack. When method call C executes, it does not make any further method calls, but simply returns the value 1. When this method returns, its activation record is popped off the top of the stack. The method call at the top of the stack is now B, which continues to execute by performing method call D. The activation record for method call D is pushed onto the stack (part c of Fig. 15.9). Method call D completes without making any more method calls, and returns the value 0. The activation record for this method call is then popped off the stack. Now, both method calls made from within method call B have returned. Method call B continues to execute, returning the value 1. Method call B completes and its activation record is popped off the stack. At this point, the activation record for method call A is at the top of the stack and the method continues its execution. This method makes method call E, whose activation record is now pushed onto the stack (part d of Fig. 15.9). Method call E completes and returns the value 1. The activation record for this method call is popped off the stack, and once again method call A continues to execute. At this point, method call A will not be making any other method calls, and can finish its execution, returning the value 2 to A's caller (Fib(3) = 2). A's activation record is popped off the stack. Note that the current method executing is always the method whose activation record is at the top of the stack, and that the activation record for that method contains the values of the method's local variables.
Introduction to Computers, the Internet and the World Wide Web
Introduction to Java Applications
Introduction to Classes and Objects
Control Statements: Part I
Control Statements: Part 2
Methods: A Deeper Look
Classes and Objects: A Deeper Look
Object-Oriented Programming: Inheritance
Object-Oriented Programming: Polymorphism
GUI Components: Part 1
Graphics and Java 2D™
Files and Streams
Searching and Sorting
Introduction to Java Applets
Multimedia: Applets and Applications
GUI Components: Part 2
Accessing Databases with JDBC
JavaServer Pages (JSP)
Strings, Characters and Regular Expressions
Appendix A. Operator Precedence Chart
Appendix B. ASCII Character Set
Appendix C. Keywords and Reserved Words
Appendix D. Primitive Types
Appendix E. (On CD) Number Systems
Appendix F. (On CD) Unicode®
Appendix G. Using the Java API Documentation
Appendix H. (On CD) Creating Documentation with javadoc
Appendix I. (On CD) Bit Manipulation
Appendix J. (On CD) ATM Case Study Code
Appendix K. (On CD) Labeled break and continue Statements
Appendix L. (On CD) UML 2: Additional Diagram Types
Appendix M. (On CD) Design Patterns
Appendix N. Using the Debugger
Inside Back Cover