5.6 Introduction to Recursion

Prerequisites: Methods, Call Stack, and Loops

Estimated time: 25 minutes

You are ready to continue when: You can write base case, recursive steps, progress measurement, and input boundaries

"Don't treat each branch as a new problem. Define how to handle a tree, then have the same method handle the subtree."

Recursion is When a Method Calls Itself Directly or Indirectly

Factorial definition:

0! = 1
n! = n × (n - 1)! for n > 0

static long factorial(int value) {
    if (value < 0) {
        throw new IllegalArgumentException("negative value: " + value);
    }
    if (value > 20) {
        throw new ArithmeticException("factorial exceeds long: " + value);
    }
    if (value == 0) {
        return 1L;
    }
    return Math.multiplyExact(value, factorial(value - 1));
}

Three parts are essential:

Part	Factorial Example	What to Prove
Input Domain	0 <= value && value <= 20	How out-of-domain inputs fail
Base Case	value == 0	No Recursion and Correct Result
Recursive Step	factorial(value - 1)	Subproblem is Smaller, Eventually Reaching the Base Case

Writing only the base case is not enough. If the recursive step passes value + 1, it will never get close to 0. A strictly decreasing, clearly bounded progress measure is needed.

Hand-Drawn factorial(4)

factorial(4)
4 × factorial(3)
4 × 3 × factorial(2)
4 × 3 × 2 × factorial(1)
4 × 3 × 2 × 1 × factorial(0)
4 × 3 × 2 × 1 × 1 = 24

Create calls in downward stages, and once the base case is reached, return layer by layer. Each layer also retains its own value and the work of "multiply once the child call returns".

Numerical Boundaries vs. Recursive Boundaries

The largest factorial that fits in long is 20!. The input check rejects values above 20 with ArithmeticException before a huge input can exhaust the stack; Math.multiplyExact still checks each multiplication. Even if the call stack can continue, the result type is already too small to hold it.

System.out.println(factorial(20));
// System.out.println(factorial(21)); // Integer overflow

Use BigInteger for larger factorials, but input and time remain restricted.

Iterative Versions Are Usually More Suitable for Linear Problems

static long factorialLoop(int value) {
    if (value < 0) {
        throw new IllegalArgumentException("negative value: " + value);
    }
    if (value > 20) {
        throw new ArithmeticException("factorial exceeds long: " + value);
    }
    long result = 1L;
    for (int factor = 2; factor <= value; factor++) {
        result = Math.multiplyExact(result, factor);
    }
    return result;
}

Both versions have a time complexity of O(n). The recursive version has an O(n) active call depth, while the iterative version uses a fixed number of local states. Java does not guarantee tail call elimination, so linear counting is typically preferred for iterative approaches.

Recursive approaches are more natural in scenarios with recursive structures: syntax trees, directory trees, composite structures, and divide-and-conquer intervals. Even so, it's important to evaluate maximum depth, cyclic references, and resource failures.

Data That Looks Like a Tree Can Contain Cycles

Object graphs, symbolic links, and dependency graphs may revisit nodes that have already been accessed. A "leaf node base case" alone is insufficient to guarantee termination; a visited set, depth limit, or domain guarantee is also required.

static void visit(Node node, Set<Node> visited) {
    if (!visited.add(node)) {
        return;
    }
    for (Node child : node.children()) {
        visit(child, visited);
    }
}

This is a structural sketch; later chapters introduce Node and Set. Assume non-null nodes and child collections and no structural changes during traversal. The visited set’s equality rule also matters: object identity and a business identifier may represent different notions of a repeated node.

Professional Quick Reference

Check Item	Question
Input Domain	How to handle negative numbers, null values, and large inputs
Base Case	Does it cover the minimum valid structure
Progress	Is each step strictly approaching the base case
Depth	Is the worst-case call depth controllable
Numerical	Does the result type overflow first
Graph Structure	Is it possible to form a cycle or repeated access

Before Moving On

Mark the input domain, base case, recursive steps, and strict descent as progress metrics using factorial(4). Explain why the factorial of 21 encounters a numerical boundary first and why the object graph still needs access records. For linear problems, you should also be able to explain how the loop version completes the same computation using a fixed number of local states.

→ Next: Recursion Stack, Redundant Calculations, and Tail Calls