Skip to main content
Logo image

Problem Solving with Algorithms and Data Structures using Java: The Interactive Edition

Section 4.6 Stack Frames: Implementing Recursion

Suppose that instead of concatenating the result of the recursive call to convert with the string from digitStrings, we modified our algorithm to push the strings onto a stack instead of making the recursive call. The code for this modified algorithm is shown in Listing 4.6.1.
Listing 4.6.1. Converting an Integer to a String Using a Stack
Each time we go through the first while loop in lines 9–16, we push a character on the stack. When converting 13 to base 2, we see that when the loop exits, the stack would look like Figure 4.6.2. Now we can pop the characters off the stack and concatenate them into the final result, "1101".
Figure 4.6.2. Strings Placed on the Stack During Conversion
The previous example gives us some insight into how Java implements a recursive method call. When a method is called in Java, a stack frame is allocated to handle the local variables of the method. When the method returns, the return value is left on top of the stack for the calling method to access. Figure 4.6.3 illustrates the call stack after the return statement on line 9.
Figure 4.6.3. Call Stack Generated from convert(13, 2)
Notice that the call to convert(2 / 2, 2) defined in Listing 4.4 leaves a return value of "1" on the stack because we have reached a base case. This return value is then used in place of the method call (convert(1, 2)) in the expression "1" + convert[3 % 2], which will leave the string "11" on the top of the stack. In this way, the Java call stack takes the place of the stack we used explicitly in Listing 4.6.1. In our array-summing example, you can think of the return value on the stack taking the place of an accumulator variable.
The stack frames also provide a scope for the variables used by the method. Even though we are calling the same methodd over and over, each call creates a new scope for the variables that are local to the method.
You have attempted of activities on this page.