Recursion Basics

Recursion is a function that solves a problem by calling itself on a smaller version of the same problem. Merge Sort and Quick Sort — which you've already coded — are both recursive. So are tree traversals, backtracking, and a large share of dynamic programming solutions still to come. Understanding recursion properly now, including exactly what happens on the call stack and exactly when it becomes dangerous, pays off for the rest of this track.

Base Case and Recursive Case

Every correct recursive function has exactly two parts:

• Base case: the condition that stops the recursion and returns a direct answer, with no further recursive call.
• Recursive case: the step that breaks the problem into a smaller version of itself and calls the function again.

public class Factorial {
    public static long factorial(int n) {
        if (n == 0 || n == 1) {          // base case
            return 1;
        }
        return n * factorial(n - 1);       // recursive case
    }

    public static void main(String[] args) {
        System.out.println(factorial(4)); // 24
    }
}

Time complexity: O(n) — one call per value from n down to 1. Space complexity: O(n) — each call adds a frame to the call stack, and n frames exist at the deepest point before any of them return.

The Call Stack, Traced Frame By Frame

Every function call — recursive or not — pushes a new stack frame onto the call stack, holding that call's local variables and its return address. A recursive call is no different from any other call in this respect; the only unusual thing is that the function keeps calling itself, so frames pile up until the base case is hit. Here's factorial(4) traced step by step.

The key idea: factorial(4) cannot compute 4 * factorial(3) until factorial(3) actually returns a value. So the call stack grows all the way down to the base case before any multiplication happens, and then the multiplications happen on the way back up, in reverse order of the calls.

Stack Overflow Risk

The JVM allocates a fixed-size stack per thread (a few hundred KB to a few MB by default, tunable with -Xss). Every recursive call that hasn't returned yet occupies a frame on that stack. If the recursion is too deep — or never reaches its base case at all — you exhaust that stack and the JVM throws StackOverflowError.

public static long badFactorial(int n) {
    // BUG: missing base case entirely
    return n * badFactorial(n - 1);
}
// badFactorial(5) -> badFactorial(4) -> badFactorial(3) -> ... -> badFactorial(-2147483648)
// -> keeps going, never stops -> StackOverflowError

Time complexity: undefined — it never terminates normally. Space complexity: O(stack limit) — grows one frame per call until the JVM's fixed thread stack size is exhausted, then crashes.

Tail Recursion — and Why Java Doesn't Optimize It

A recursive call is tail recursive when the recursive call is the very last operation in the function — nothing happens after it returns. Some languages (Scheme, and to a degree Scala/Kotlin with an explicit annotation) detect this pattern and rewrite it into a loop at compile time, so it runs in O(1) stack space no matter how deep the recursion goes. This is called tail-call optimization (TCO).

// This LOOKS tail recursive: the recursive call is the last thing that happens.
public static long factorialTail(int n, long accumulator) {
    if (n == 0) {
        return accumulator;
    }
    return factorialTail(n - 1, n * accumulator); // tail call
}

public static long factorialIterative(int n) {
    long result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

Time complexity: O(n) — same work as the recursive version. Space complexity: O(1) — one loop variable and one accumulator, no call stack growth, which is exactly the property tail-call optimization would have given us automatically in a language that supports it.

Worked Example: Naive vs Memoized Fibonacci

This is the classic example for showing that "correct" recursion and "efficient" recursion are not the same thing — and it sets up the motivation for dynamic programming later in this track.

// Naive: recomputes the same subproblems over and over
public static long fibNaive(int n) {
    if (n <= 1) {
        return n;
    }
    return fibNaive(n - 1) + fibNaive(n - 2);
}

fibNaive(5) calls fibNaive(4) and fibNaive(3). But fibNaive(4) itself calls fibNaive(3) again — so fibNaive(3) gets computed twice from scratch, fibNaive(2) gets computed three times, and so on. The call tree branches into roughly 2ⁿ total calls.

Time complexity: O(2ⁿ) — the call tree has two branches at every level down to depth n, and almost all of that work is duplicate. Space complexity: O(n) — the deepest single chain of pending calls (the recursion depth), even though the total number of calls is exponential.

import java.util.HashMap;
import java.util.Map;

// Memoized: cache each subproblem's answer the first time it's computed
public static long fibMemo(int n, Map<Integer, Long> cache) {
    if (n <= 1) {
        return n;
    }
    if (cache.containsKey(n)) {
        return cache.get(n);        // already solved -> O(1) lookup, no recursion
    }
    long result = fibMemo(n - 1, cache) + fibMemo(n - 2, cache);
    cache.put(n, result);
    return result;
}

// Call site:
long answer = fibMemo(50, new HashMap<>());

Time complexity: O(n) — each value from 0 to n is computed exactly once and then reused from the cache for every subsequent request. Space complexity: O(n) — the cache holds one entry per subproblem, plus O(n) recursion depth.

Recursion vs Iteration — Choosing Deliberately