Recursion is a method that calls itself on a smaller version of the same problem. It has exactly two parts, and every recursion bug is one of them being wrong.
The two parts
- A base case that returns without recursing.
- A recursive case that makes progress towards the base case.
public static long factorial(int n) {
if (n < 0) {
throw new IllegalArgumentException("factorial of a negative number");
}
if (n <= 1) {
return 1; // base case
}
return n * factorial(n - 1);
}Miss the base case, or fail to move towards it, and you get
StackOverflowError. That is not a mysterious failure — it is the runtime telling you
the base case is never reached.
The guard on negatives matters for the same reason: factorial(-1) would recurse
towards minus infinity, never hitting n <= 1. An input the base case cannot catch is
an infinite recursion in disguise.
What the stack is doing
Each call pushes a frame — parameters, locals, return address — onto the call stack. Nothing is computed on the way down; the multiplication happens on the way back up.
factorial(4)
4 * factorial(3)
3 * factorial(2)
2 * factorial(1)
1 base case reached, unwinding
2 * 1 = 2
3 * 2 = 6
4 * 6 = 24Four frames alive at once. That is the cost recursion has and iteration does not.
⚠️ The stack is small, and Java has no tail-call optimisation
A thread's stack is typically 512 KB to 1 MB — a few thousand frames, sometimes tens of thousands. Some languages recognise that a method whose last act is the recursive call needs no new frame and reuse it. Java does not, even when the call is in tail position. So depth is bounded, always:
// The stack is finite, and that is a fact worth demonstrating rather than asserting.
Check.threw(() -> deepRecursion(1_000_000), StackOverflowError.class,
"a million frames overflows the stack");The practical rule: if the recursion depth scales with n, and n can be large, use a loop. Depth that scales with log n — binary search, a balanced tree — is fine forever, because log₂ of a billion is thirty.
When a loop is better
/** The same job as a loop, to make the trade-off concrete: no stack, but less direct. */
public static long factorialIterative(int n) {
long result = 1;
for (int i = 2; i <= n; i++) {
result *= i;
}
return result;
}Same answer, no stack growth, marginally faster. For factorial the loop is simply better, and factorial is the example everyone teaches recursion with — which is a bit of a joke on the subject.
When recursion is better
When the problem is recursive. Trees, graphs, nested structures, backtracking — anything defined in terms of smaller copies of itself. Towers of Hanoi is the clearest case: the iterative solution exists and nobody can read it.
private static void hanoi(int n, char from, char to, char via, List<String> moves) {
if (n == 0) {
return;
}
hanoi(n - 1, from, via, to, moves);
moves.add(n + ":" + from + "->" + to);
hanoi(n - 1, via, to, from, moves);
}Three lines say the whole thing: move n−1 discs out of the way, move the big one, move n−1 back. The move count is 2ⁿ − 1, which the tests check at several sizes rather than trusting the formula:
Check.eq(hanoi(3).size(), 7, "three discs is 2^3 - 1");
Check.eq(hanoi(10).size(), 1023, "ten discs is 2^10 - 1");Tree traversal is the same story — the tree post writes in-order traversal in four lines recursively, and the iterative version needs an explicit stack to simulate what the call stack was doing for free.
⚠️ Correct and still useless
public static long fibonacciNaive(int n) {
if (n < 2) {
return n;
}
return fibonacciNaive(n - 1) + fibonacciNaive(n - 2);
}Perfectly correct, and unusable. Each call spawns two more, so this is O(2ⁿ):
fib(50) would take longer than a lunch break, and it is recomputing
fib(30) over a million times.
The problem is not recursion, it is repeated recursion over overlapping subproblems. Remember each answer and the same shape becomes O(n) — which is dynamic programming, and the single biggest speedup in this track.
Two shapes worth recognising
Two pointers moving inwards — the recursive form of a scan from both ends:
private static boolean palindrome(String s, int low, int high) {
if (low >= high) {
return true;
}
if (s.charAt(low) != s.charAt(high)) {
return false;
}
return palindrome(s, low + 1, high - 1);
}Build the result on the way back up — nothing accumulates going down:
public static String reverse(String s) {
if (s.length() <= 1) {
return s;
}
return reverse(s.substring(1)) + s.charAt(0);
}That one is a nice illustration and a bad implementation: each call allocates a new substring, so
it is O(n²) in both time and memory. new StringBuilder(s).reverse() is what you would
actually write. Recursion being elegant does not make it efficient.
How to reason about one
Do not trace the whole call tree in your head — that is what makes recursion feel hard. Check three things instead:
- Is there a base case, and does every input path reach it?
- Does each recursive call make the problem strictly smaller?
- Assuming the recursive call is correct, is the combination correct?
Step 3 is the leap worth practising. Trust the recursive call to do its job and only verify the one level in front of you. It feels like cheating and it is exactly how induction works.
What to remember
- Base case plus progress towards it.
StackOverflowErrormeans one is missing. - Java has no tail-call optimisation, so depth is bounded by a small stack.
- Depth that scales with n → use a loop. Depth that scales with log n → fine.
- Reach for recursion when the data is recursive: trees, graphs, backtracking.
- Overlapping subproblems mean memoise, or the elegance costs you O(2ⁿ).