Section 12.2 The Call Stack
A running method must pause when it invokes another method. The state of a paused method must be saved so that when the invoked method returns the invoking method can pick up where it left off.
The state of all active methods is saved in an internal data structure called a stack frame. A stack frame tracks an active method’s scope (variables and their instantaneous values) and on which instruction to resume execution when the invoked method completes. There are as many stack frames as your program has active methods, all of which are stored in another data structure called the call stack. To visualize a call stack, think of a stack of clean dinner plates. Typically, you add to the top of a stack, and remove from the top of the stack. It is the same with the call stack data structure. When a new stack frame (dinner plate) is created as a result of one method invoking another, the stack frame is pushed onto the top of the call stack. When the invoked method completes, the stack frame describing the paused method is popped off the top of the stack and used to resume execution.
Each active method has a stack frame that tracks its state. This is the case even when a method invokes itself — the new method invocation gets a new stack frame. This is what happens when executing a recursive method. Consider the recursive method
countdown(int n) in Listing 12.2.1.public class LiftOff {
public static void main(String[] args) {
countdown(10);
}
// Count down from N
public static void countdown(int N) {
// When N reaches 0, Lift Off!
if (N <= 0) {
System.out.println("We have lift off!");
// Print current count and recurse with decremented value
} else {
System.out.println(N);
countdown(N-1);
}
}
}
ListOff.javajavac LiftOff.java java LiftOff 10 9 8 7 6 5 4 3 2 1 We have lift off!
Each time the else-branch in the
countdown(…) method in Listing 12.2.1 is invoked, the state of the invoking method is captured in a stack frame and pushed on the call stack. During recursion this repeats itself with each new value of N until the base case is reached. Figure 12.2.2 is an illustrative diagram of the call stack when this recursion hits the base case. All stack frames hold the current value of N when it pauses. After reaching the base case, each paused method returns in reverse order, which pops the next stack frame off the top of the call stack, returning control to the paused method.Every one of the stack frames depicted in Figure 12.2.2 represents an active version of the
countdown(…) method. Recursion works because each newly invoked method has its own scope and its own set of method-scoped variables, even when the method invoked is the same as the invoking method.
A wonderful tool for visualizing the call stack in action is the Java Visualizer 1 , one instance of which is hosted by the University of Waterloo Centre for Education in Mathematics and Computing. You can paste a small Java program into the editor of this tool and watch it execute, step-by-step. The current state of the call stack is illustrated on the right as you step through the program animation. Figure 12.2.3 below is an embedded version of the visualizer for the
LiftOff.java program. Scroll to the right to see the call stack. Drag left the right edge of the editor window to bring both into view. Click the [Forward] button to step through the program. Alternatively, click here 2 to visualize the program on the site, directly.Try your own programs by visiting the Java Visualizer 3 site.
What happens if we make an error in the base case condition, or forget it altogether? Let’s test it by making a second version of
LiftOff.java with the base case commented out. See Listing 12.2.4 and its console session.// NoBaseCase.java
public class NoBaseCase {
public static void main(String[] args) {
countdown(10);
}
// Count down from N
public static void countdown(int N) {
// When N reaches 0, Lift Off!
// if (N <= 0) {
// System.out.println("We have lift off!");
// // Print current count and recurse with decremented value
// } else {
System.out.println(N);
countdown(N-1);
// }
}
}
NoBaseCase.javajavac NoBaseCase.java
java NoBaseCase
10
9
8
7
6
5
4
3
2
1
0
-1
-2
-3
…
-14396
-14397
-14398
Exception in thread "main" java.lang.StackOverflowError
at java.base/java.nio.CharBuffer.wrap(CharBuffer.java:408)
at java.base/sun.nio.cs.StreamEncoder.implWrite(StreamEncoder.java:281)
at java.base/sun.nio.cs.StreamEncoder.write(StreamEncoder.java:132)
at java.base/java.io.OutputStreamWriter.write(OutputStreamWriter.java:205)
at java.base/java.io.BufferedWriter.flushBuffer(BufferedWriter.java:120)
at java.base/java.io.PrintStream.writeln(PrintStream.java:722)
at java.base/java.io.PrintStream.println(PrintStream.java:938)
at NoBaseCase.countdown(NoBaseCase.java:15)
at NoBaseCase.countdown(NoBaseCase.java:16)
at NoBaseCase.countdown(NoBaseCase.java:16)
at NoBaseCase.countdown(NoBaseCase.java:16)
at NoBaseCase.countdown(NoBaseCase.java:16)
at NoBaseCase.countdown(NoBaseCase.java:16)
at NoBaseCase.countdown(NoBaseCase.java:16)
at NoBaseCase.countdown(NoBaseCase.java:16)
at NoBaseCase.countdown(NoBaseCase.java:16)
…
The two ellipses (…) in the previous console session output show where many lines have been deleted. The call stack built up about 14,400+ stack frames before it overflowed and threw an error. The line right after the last countdown value was printed shows the
java.lang.StackOverflowError and a very long dump of the call stack, which includes the 14,400+ recursive calls at line 16 of NoBaseCase.java. The call stack does not have infinite memory in which to hold all stack frames. This is what happens when it runs out.cscircles.cemc.uwaterloo.ca/java_visualize/cscircles.cemc.uwaterloo.ca/java_visualize/#code=public+class+LiftOff+%7B%0A++public+static+void+main(String%5B%5D+args)+%7B%0A++++countdown(10)%3B%0A++%7D%0A%0A++//+Count+down+from+N%0A++public+static+void+countdown(int+N)+%7B%0A++++//+When+N+reaches+0,+Lift+Off!%0A++++if+(N+%3C%3D+0)+%7B%0A++++++System.out.println(%22We+have+lift+off!%22)%3B%0A%0A++++//+Print+current+count+and+recurse+with+decremented+value%0A++++%7D+else+%7B%0A++++++System.out.println(N)%3B%0A++++++countdown(N-1)%3B%0A++++%7D%0A++%7D%0A%7D&mode=displaycscircles.cemc.uwaterloo.ca/java_visualize/
