Recursion — cheat sheet

General CS fundamentals, no course slide source — written directly, same as 01-big-o-notation.md.

What it is

A function that calls itself to solve a smaller instance of the same problem. Every recursive function needs two parts:

• Base case — the condition that stops the recursion and returns directly, without calling itself again.
• Recursive case — calls itself with a smaller/simpler input, moving toward the base case.

Miss either part (no base case, or a recursive case that never actually shrinks toward it) and you get infinite recursion — in Java, a StackOverflowError.

How it actually runs

Each call adds a frame to the call stack. Calls keep stacking up until the base case is hit, then each frame returns and unwinds back up, combining results on the way. This is also why recursion has a real, often-overlooked cost: O(depth) extra space on the call stack, on top of whatever the algorithm's own logic costs.

Classic examples

// Base case: n <= 1. Recursive case: n * factorial(n - 1)
int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

// Base case: n <= 1. Recursive case: fib(n-1) + fib(n-2)
int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Naive recursive Fibonacci is a classic Big O trap: it's O(2ⁿ), because computing fib(n) recomputes fib(n-2) twice (once directly, once inside fib(n-1)), and that duplication compounds at every level. Fixable with memoization (caching already-computed results) or an iterative loop — worth mentioning if asked, since "why is this slow and how would you fix it" is a natural interview follow-up.

// Sum of a list, recursively
int sum(List<Integer> numbers) {
    if (numbers.isEmpty()) return 0;
    return numbers.get(0) + sum(numbers.subList(1, numbers.size()));
}

Recursion vs iteration

• Anything recursive can be rewritten as a loop, and vice versa.
• Recursion tends to read more naturally for structurally recursive data — trees, nested JSON, directory trees — where "the same operation, on a smaller sub-structure" is a direct match for the data's own shape.
• Iteration is usually more efficient in Java: no extra call-stack frames, no risk of StackOverflowError on deep input.
• Tail recursion (where the recursive call is the very last thing the function does) is optimized into a plain loop by some languages/compilers — Java does not do this optimization, so even a "tail-recursive-style" Java function can still overflow the stack on deep enough input. Don't rely on tail-call optimization existing in Java.

How to approach writing one (interview framing)

1. What's the base case — the smallest input you can answer immediately?
2. How does one step reduce the problem toward that base case?
3. Trust the recursive call to correctly solve the smaller problem (don't try to mentally unwind the whole stack) — just work out how to combine its result with the current step.

Be ready to write a small one on the spot (factorial, Fibonacci, reversing a string, summing a list) and to state its time and space complexity afterward.