Session 19 — Recursion and the call stack

Recursion means a method calls itself on a smaller or simpler subproblem until a base case stops the chain. This session builds reliable recursive thinking: how the call stack grows, why missing bases cause StackOverflowError, and when iteration is the safer engineering choice.

Time: about 85 minutes.

1. Structure of a recursive method

Every recursive definition has:

1. Base case — returns immediately without another self-call (often trivial input size).
2. Recursive step — calls itself with progress toward the base (smaller n, shorter array slice, left/right subtree).

public static long factorial(int n) {
    if (n < 0) {
        throw new IllegalArgumentException("n must be non-negative");
    }
    if (n <= 1) {
        return 1; // base
    }
    return n * factorial(n - 1); // recurse toward 0/1
}

---

2. Call stack intuition

Each active method call consumes a stack frame holding parameters, locals, and return address. Deep recursion means many simultaneous frames—finite stack memory. Fibonacci implemented as fib(n)=fib(n-1)+fib(n-2) is both deep and exponentially branching—avoid as a production pattern; it is fine as a cautionary tale.

---

3. Classic patterns

• Divide and conquer — merge sort, binary search (binary search is often written iteratively, but the recursive version illustrates halving).
• Tree walks — later data-structure courses; recursion mirrors the shape of the tree.
• Backtracking — explore choices, undo on failure (puzzle solvers).

---

4. Tail recursion note

Some languages eliminate tail calls (recursive call is the last action). Java does not guarantee tail-call optimisation—do not rely on it for arbitrarily deep linear recursion. Convert to a while loop with explicit stack when depth is large.

---

5. Mutual recursion

Method A calls B which calls A again—still needs bases reachable from both sides. Less common in first courses but appears in parsers.

---

6. Pitfalls

• Missing or wrong base → infinite recursion → StackOverflowError.
• No progress toward base (e.g. countdown(n) calls countdown(n)) → same failure.
• Large hidden constants — recursion depth n on stack size ~O(n); iteration is O(1) stack.

---

7. Debugging trick

Log entry with indentation proportional to depth, or pass a depth parameter and guard with a maximum to fail fast while learning.

Example A — list length without a loop (pedagogical)

import java.util.List;

public class Len {
    public static <T> int length(List<T> items) {
        return lengthFrom(items, 0);
    }

    private static <T> int lengthFrom(List<T> items, int index) {
        if (index == items.size()) {
            return 0;
        }
        return 1 + lengthFrom(items, index + 1);
    }
}

The base is index == size; the step increments index—progress is obvious.

---

Example B — binary search (sorted array)

public class Search {
    public static int indexOf(int[] sorted, int key) {
        return indexOfRange(sorted, key, 0, sorted.length);
    }

    private static int indexOfRange(int[] sorted, int key, int lo, int hi) {
        if (lo >= hi) {
            return -1;
        }
        int mid = (lo + hi) >>> 1;
        int v = sorted[mid];
        if (v == key) {
            return mid;
        }
        if (v < key) {
            return indexOfRange(sorted, key, mid + 1, hi);
        }
        return indexOfRange(sorted, key, lo, mid);
    }
}

Each recursive call halves the range—depth O(log n) frames, safe for large arrays compared to naive linear recursion.