Recursion and the Method Call Stack

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.