Recursion, Deep
Base case and recursive case, the call stack, and how to trust and design a recursive solution instead of tracing it in your head.
On this page
Recursion is the foundation for backtracking and dynamic programming, the two patterns that intimidate people most. Before those, this lesson builds real fluency with recursion itself: how to design a recursive solution (rather than trace one in your head), the anatomy of a recursive call, and the mindset that makes hard recursion feel natural.
Base case and recursive case
Every recursion has two parts: a base case that stops the recursion, and a recursive case that reduces the problem toward the base case. Miss the base case and you recurse forever (StackOverflowError); fail to shrink the problem and you never reach it.
// factorial: base case n <= 1; recursive case reduces n
long factorial(int n) {
if (n <= 1) return 1; // base case
return n * factorial(n - 1); // recursive case: smaller problem
}Design it; don't trace it
The mental leap that makes recursion click: don't try to follow the calls in your head. Instead, assume the recursive call already returns the correct answer for a smaller input, and just define how to build your answer from it. Three questions design any recursion:
- What's the smallest input I can answer directly? (base case)
- If I had the answer for a smaller input, how would I extend it? (recursive case)
- Does each call move toward the base case? (termination)
For "reverse a string," the smallest input is the empty string; if you can reverse the tail, prepend the first character:
String reverse(String s) {
if (s.isEmpty()) return s; // base case
return reverse(s.substring(1)) + s.charAt(0); // trust the smaller reverse, extend it
}You never mentally unwound the whole recursion - you trusted reverse(s.substring(1)) and only decided
the combine step. That trust is the skill.
The call stack, remembered
From the complexity module: each recursive call adds a stack frame, so recursion of depth d uses O(d) space. Deep recursion on large inputs risks a stack overflow, which is why some recursions are rewritten as loops or given an explicit stack. Keep depth in mind as part of a recursion's cost.
Recursion that recomputes is a trap - and a signpost
Naive recursion sometimes solves the same subproblem many times. Fibonacci is the classic: fib(n) = fib(n-1) + fib(n-2) recomputes fib values exponentially, making it O(2^n). That waste isn't just a bug - it's the signal that dynamic programming (remembering answers) applies, which the next lessons build on.
Opening a set of nesting dolls, you don't plan every doll at once. You open the outer one, and inside is a smaller version of the exact same task: open this doll. You trust that 'opening the inner doll' will work the same way, all the way down to the tiny solid doll that doesn't open (the base case). Recursion is that self-similar structure: each call is a smaller instance of the same problem, and you only reason about one level - open the current doll, then trust the rest - not the whole nested set.
Write a recursive function to compute x raised to the n (x^n) for non-negative n. First give the straightforward O(n) version by designing the base and recursive cases, then describe how to make it O(log n).
What is the recommended way to design a recursive solution?
Key takeaways
- Every recursion needs a base case (to stop) and a recursive case (that shrinks the problem toward it).
- Design recursion by trusting that the recursive call solves a smaller input, then defining the combine step - don't trace it mentally.
- Three questions: smallest directly-answerable input? how to extend a smaller answer? does each call move toward the base?
- Each call costs a stack frame, so depth-d recursion is O(d) space; deep recursion risks stack overflow.
- Recursion that recomputes the same subproblem (like naive Fibonacci, O(2^n)) is the signal that dynamic programming applies.