JentooComputer Science A

AP® Computer Science A · Unit 4 · Topic 4.16

Base Cases and StackOverflowError

A base case is the condition that stops recursion; without one that the calls actually reach, each call pushes another frame onto the stack until it runs out of space and crashes with a StackOverflowError.

Watch it drawn4 questionsPractice

A loop with no update just spins forever using the same bit of memory. Recursion is different: every call, even an identical-looking one, gets its own fresh frame on the call stack, holding its parameters and local variables and a note on where to return. The stack has a fixed size. If a recursive method never hits a base case, it keeps calling itself, and the runtime keeps stacking new frames on top of old ones. Nothing ever gets popped off, because nothing ever returns. Eventually there is no room left, and the program throws a StackOverflowError instead of looping quietly.

Having a base case written in the code is not the same as the recursion reaching it. The calls have to progress toward that condition, getting closer with each step. If the arguments move the wrong direction, or skip over the base case entirely, the base case sits there unused while the stack fills up anyway. This is why tracing the progression of the argument matters as much as spotting the base case itself.

This sits right after you learn the mechanics of recursive calls and returns, and right before recursion with multiple base cases, where a method might need to stop on more than one condition to cover every path the arguments can take.

Key terms

Base case
The condition in a recursive method that stops further recursive calls and returns directly.
Call stack
The fixed-size region of memory holding one frame per active method call, most recent on top.
Stack frame
The block of memory storing one call's parameters, local variables, and return location.
StackOverflowError
The error thrown when the call stack runs out of space for new frames.

Watch it explained

  1. How it worksHow does an unbounded chain of frames fill the stack until it finally gives out?
  2. Worked exampleTrace a countdown method that recurses on n - 1 but tests n == 1, called with 0.
  3. Common mistakeWhy doesn't having a base case guarantee that the recursion ever reaches it?
  4. Going furtherWhat changes when a recursive method has two base cases instead of one?

Check yourself

Your turn1 of 2
Why does a missing base case in a recursive method crash the program with a StackOverflowError, instead of just looping forever the way a missing update in a while loop does?

End of topic.

Next: Binary Search: Halving the Range →