Chapter 7 — Recursion

“For from him and through him and to him are all things. To him be glory forever. Amen.” — Romans 11:36

“To understand recursion, you must first understand recursion.” — programmer folk wisdom

Why This Matters

Some problems are loops. Some problems are recursion.

A loop is the shape of “do this to each thing in a list.” A recursion is the shape of “this problem contains a smaller version of itself.” Most students reach for a loop reflexively, because loops were the first repetition tool you met. That reflex is fine for loop-shaped problems. It is catastrophic for recursion-shaped problems — problems where you cannot know how deep you’ll need to go because the shape of the data tells you, and the shape of the data is, itself, recursively defined.

A directory contains files. It also contains subdirectories. Each subdirectory contains files. And subdirectories. To walk the tree, you do not need a loop with a counter. You need a function that knows how to handle one directory — by handling each child, and for each child that is itself a directory, calling itself. The function is recursive because the data is recursive.

Recursion is the conceptual tool for self-similar problems. It is also the mental model that will make trees, graphs, and the algorithms that walk them feel natural when you meet them in Coding 3. For Coding 2, we are not building data structures. We are learning to think in the shape that the structures will demand.

The Christian framing is the most contemplative of the semester. When does the part contain the whole? The doctrine of the body of Christ in 1 Corinthians 12 — the part is not the whole, but each part bears something of the whole’s life. The image of God in Genesis 1 — each human, finite and part-like, somehow bears the imprint of the infinite. The fractal beauty of creation, where snowflakes and coastlines and lung tissue all repeat their own shapes at every scale. The part contains the whole. That is the shape of recursion, and the shape of more than recursion.

7.1 — The Anatomy of a Recursive Function

Every recursive function has exactly two pieces.

1. A base case — the smallest version of the problem, which you solve directly without recursing.
2. A recursive case — the larger version, which you solve by reducing it to a smaller version of the same problem and asking the function to solve that.

If you forget the base case, the function recurses forever and you get StackOverflowError. If you forget to reduce in the recursive case, same thing — you call yourself with the same input and recurse forever. The two pieces, present and correct, is the entire discipline.

Here is the canonical first example: factorial.

public static int factorial(int n) {
    if (n <= 1) return 1;            // base case: 0! and 1! are both 1
    return n * factorial(n - 1);     // recursive case: n! = n * (n-1)!
}

Read it slowly.

• The base case: when n <= 1, return 1 directly. No recursion.
• The recursive case: when n is larger, return n times the factorial of n - 1. That smaller call will eventually hit the base case.

Trace factorial(4):

factorial(4) = 4 * factorial(3)
             = 4 * (3 * factorial(2))
             = 4 * (3 * (2 * factorial(1)))
             = 4 * (3 * (2 * 1))
             = 4 * (3 * 2)
             = 4 * 6
             = 24

Each call waits for its child call to return, multiplies by n, and returns its own answer up to its caller. The whole chain unwinds when the base case is hit. Hold this trace in your head. It is the mental model for every recursion you will ever write.

Coach’s Note — Write the base case first. Always. Many recursive bugs come from writing the interesting recursive case before defining the boundary that stops the recursion. Base case first, then the step toward it.

7.2 — The Stack and the Frame

Every time a method calls another method (recursively or not), the JVM allocates a stack frame to hold that method’s local variables, parameters, and the address to return to. The frames stack on top of each other. When the called method returns, its frame is popped off, and execution resumes in the caller.

A recursive function builds a tall stack. factorial(4) lives in a frame; while it waits for factorial(3) to return, factorial(3) lives in its own frame on top. The total stack depth equals the recursion depth.

This matters because the stack has a finite size. By default, the JVM gives each thread roughly half a megabyte of stack space, which translates to thousands of recursive frames before you run out. For most well-formed recursion in this course, you have all the headroom you need. For pathological cases — factorial(1_000_000), or recursion that doesn’t reduce, or recursion on a million-deep linked list — you’ll see:

Exception in thread "main" java.lang.StackOverflowError
    at Demo.factorial(Demo.java:3)
    at Demo.factorial(Demo.java:3)
    at Demo.factorial(Demo.java:3)
    ... 8000 more

The signature ... N more ellipsis is Java’s way of saying “this stack trace would have been miles long, here’s the rest.” When you see it, suspect recursion that doesn’t terminate (forgot the base case, or didn’t reduce) — or recursion that does terminate but is just too deep for this problem (use iteration, see §7.6).

7.3 — Mathematical Recursion: Three Classics

Three problems that are born recursive in their definitions. Each rewards the recursive solution with clearer code than the iterative version.

Greatest Common Divisor — Euclidean Algorithm

The mathematical definition: gcd(a, b) = b when a mod b == 0, otherwise gcd(a, b) = gcd(b, a mod b).

public static int gcd(int a, int b) {
    if (b == 0) return a;           // base case
    return gcd(b, a % b);           // recursive case
}

Trace gcd(48, 18):

gcd(48, 18) → gcd(18, 12) → gcd(12, 6) → gcd(6, 0) = 6

Four lines of code. The same algorithm written iteratively works but obscures the recurrence relation. The recursive form is the math.

Fibonacci

The mathematical definition: fib(0) = 0, fib(1) = 1, fib(n) = fib(n-1) + fib(n-2).

public static long fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

This works. It also gets explosively slow for n > 40 because of redundant work — fib(38) is computed many times across the call tree. We’ll fix this in §7.8 with memoization.

Power

pow(x, n) = 1 when n == 0, otherwise x * pow(x, n-1).

public static long pow(long x, int n) {
    if (n == 0) return 1;
    return x * pow(x, n - 1);
}

A small optimization, which is also a beautiful recursion: when n is even, pow(x, n) = pow(x*x, n/2). That halves the recursion depth each step instead of decrementing by one.

public static long powFast(long x, int n) {
    if (n == 0) return 1;
    if (n % 2 == 0) return powFast(x * x, n / 2);
    return x * powFast(x, n - 1);
}

powFast(2, 1024) makes about 10 recursive calls. pow(2, 1024) makes 1024. The shape of the recursion matters, not just the fact of it.

7.4 — Structural Recursion: Walking a Nested Map

The other major family of recursion: data is recursive, so the function that walks it is recursive.

Consider a configuration represented as a nested map:

Map<String, Object> config = Map.of(
    "name", "ChurchApp",
    "version", "1.0",
    "server", Map.of(
        "host", "localhost",
        "port", 8080
    ),
    "database", Map.of(
        "primary", Map.of("host", "db1", "port", 5432),
        "replica", Map.of("host", "db2", "port", 5432)
    )
);

A printer that pretty-prints this nested structure as indented text:

public static void printNested(Map<String, Object> map, int indent) {
    String pad = "  ".repeat(indent);
    for (Map.Entry<String, Object> e : map.entrySet()) {
        System.out.print(pad + e.getKey() + ": ");
        if (e.getValue() instanceof Map<?, ?> child) {
            System.out.println();
            @SuppressWarnings("unchecked")
            Map<String, Object> typed = (Map<String, Object>) child;
            printNested(typed, indent + 1);             // recursive!
        } else {
            System.out.println(e.getValue());
        }
    }
}

Call it with printNested(config, 0) and you get:

name: ChurchApp
version: 1.0
server:
  host: localhost
  port: 8080
database:
  primary:
    host: db1
    port: 5432
  replica:
    host: db2
    port: 5432

The structure of the function mirrors the structure of the data. Each entry’s value is either a leaf (print it) or a nested map (recurse on it, with deeper indentation). The base case is implicit — the loop terminates when the current map has no more entries.

Notice the pattern-matching instanceof syntax (Java 16+): if (e.getValue() instanceof Map<?, ?> child). This both tests the type and binds a typed variable, all in one shot. It is the modern Java way to do what older Java required as a separate cast.

Coach’s Note — The pattern in §7.4 — “for each piece of structured data, if it’s a leaf, handle directly; if it’s a node, recurse” — is the universal shape of structural recursion. You will see it again when Coding 3 introduces trees. The shape is the same; only the data type changes.

7.5 — Walking a Directory Tree

Files and directories form a tree. Files are leaves. Directories are nodes that contain children, some of which are themselves directories. To find every .java file under a given root, you walk recursively.

Java offers two routes.

The built-in: Files.walk

import java.nio.file.Files;
import java.nio.file.Path;
import java.util.stream.Stream;

try (Stream<Path> stream = Files.walk(Path.of("src"))) {
    stream
        .filter(p -> p.toString().endsWith(".java"))
        .forEach(System.out::println);
}

Files.walk returns a Stream<Path> that yields every file and directory under the given root, recursively. Combined with a filter, you have a one-liner for “every .java file under src.” Behind the scenes, Files.walk is using recursion of some flavor — but the recursion is hidden inside the library.

For Project 7, the Normal tier asks you to write the walker by hand, so you can see the recursion explicitly. Then you’ll use Files.walk in real life.

The hand-rolled version

The full runnable version of this walker is here (download FileFinder.java):

import java.io.IOException;
import java.nio.file.*;

public class FileFinder {
    public static void findJavaFiles(Path dir) throws IOException {
        if (!Files.isDirectory(dir)) return;          // base case (sort of)
        try (DirectoryStream<Path> stream = Files.newDirectoryStream(dir)) {
            for (Path child : stream) {
                if (Files.isDirectory(child)) {
                    findJavaFiles(child);              // recurse
                } else if (child.toString().endsWith(".java")) {
                    System.out.println(child);
                }
            }
        }
    }
}

The structure:

• For each child of the current directory, decide: is it a directory or a file?
• If a directory, recurse into it.
• If a .java file, print it.
• Otherwise, ignore.

The base case is implicit: when the directory has no children, the for-loop body never runs, and the function returns naturally. That’s a clean base case — sometimes the absence of work is the base case.

Files.newDirectoryStream returns an iterator over the immediate children of a directory. Wrapped in try-with-resources so the underlying handle is closed even if a child recursion throws.

Coach’s Note — When students write their first directory walker, the most common bug is forgetting to handle the “this directory has no children” case explicitly. The for-loop handles it for you — but only if you wrote the for-loop. If you wrote an if (child == null) check or some other awkward thing, you may have built yourself a trap. Trust the iteration; let the empty loop be your base case.

7.6 — When Iteration Is Clearer (And When It Isn’t)

Not every recursive solution is the best solution. Sometimes iteration is shorter, faster, or just clearer.

The factorial example is the classic case where iteration is at least as readable:

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

Same answer, no stack growth, easy to read. For straightforward “accumulate over a range” problems, a loop is often the right tool.

The directory walker, by contrast, is genuinely awkward without recursion. You can convert it to an iterative version using an explicit stack (push the root, pop and process each, push children) — but you have built yourself, by hand, the very thing recursion gave you for free.

The rule of thumb:

• Reach for recursion when the data is recursive (trees, nested maps, directory hierarchies, JSON of unknown depth, the parse tree of an expression).
• Reach for iteration when the data is flat (arrays, lists, single-level maps) or the computation is a clean accumulation.

A senior engineer fluent in both will pick whichever makes the code more obvious. Knowing both — and knowing why you’d pick one — is the skill.

Tail calls (a footnote)

Some functional languages optimize tail-recursive calls into iteration automatically — no stack growth. Java does not. A function that recurses on its very last action (a “tail call”) still consumes a frame in Java. For deep recursion in Java, you must either rewrite as iteration or accept the stack depth. Coding 3 will revisit this when we look at language-design tradeoffs.

7.7 — A Word on the Call Tree

For problems like Fibonacci, the recursion is more than a stack — it’s a tree. fib(5) calls fib(4) and fib(3). fib(4) calls fib(3) and fib(2). fib(3) is being called multiple times across the tree, and each time it recomputes from scratch.

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)
│   │   └── fib(1)
│   └── fib(2)
└── fib(3)
    ├── fib(2)
    └── fib(1)

You can see fib(3) appears twice; fib(2) appears three times. The total work is exponential in n. For n = 40, that’s hundreds of millions of redundant calls. For n = 50, you’ll be waiting a long time.

Two responses:

1. Memoization — remember the answer the first time you compute it (§7.8).
2. Rewrite as iteration with a small running window of state.

Either fix turns Fibonacci from exponential to linear. Both are worth knowing.

7.8 — Memoization

Memoization is the trick of caching the result of a recursive call so that the second time you ask for the same input, you return the cached answer instead of recomputing. The runnable version is here (download FastFib.java):

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

public class FastFib {
    private static final Map<Integer, Long> CACHE = new HashMap<>();

    public static long fib(int n) {
        if (n <= 1) return n;
        if (CACHE.containsKey(n)) return CACHE.get(n);
        long result = fib(n - 1) + fib(n - 2);
        CACHE.put(n, result);
        return result;
    }
}

Two new lines do the work. Before computing, check the cache. After computing, store the result.

With memoization, fib(50) returns essentially instantly. Each fib(k) for k <= 50 is computed exactly once. The total work is linear, not exponential.

Memoization is a general technique. Any time a recursive call structure has overlap — the same sub-problem reached via multiple paths — memoization buys you back the redundancy. Coding 3 will introduce dynamic programming, which is essentially memoization formalized into a discipline of its own.

Coach’s Note — The Map cache is a HashMap here, which means the iteration order is undefined. For pure functions where you only care about lookups, that’s fine. If you ever want predictable order, use LinkedHashMap or TreeMap. Chapter 8 explains the difference in detail.

7.9 — Recursion as a Specification Tool

Once you can think recursively, you start to write cleaner specifications. Recursive descriptions are often the most natural way to describe what something is.

“A directory is a set of files and other directories.” (Recursive definition.)

“A valid expression is a number, or two valid expressions joined by an operator.” (Recursive definition.)

“A nested list is either a value, or a list of nested lists.” (Recursive definition.)

Each of these maps directly to a recursive function for processing the thing. The data shape and the function shape rhyme. When you find yourself writing a long-winded English explanation of “what is this thing?” — and the explanation keeps saying “…or another one of these inside it…” — you have found a recursive definition trying to escape.

Phase 2 of this course (specifications for AI) will reward exactly this kind of fluency. The clearest specifications are often the recursively-defined ones, because they describe the shape of the data and let the implementation follow.

7.10 — Common Bugs (Week 7 Edition)

Bug: StackOverflowError with no obvious infinite loop. What it means: A recursive call that doesn’t reduce, or a missing base case. Fix: Check the recursive case: are you calling yourself with a smaller input? Check the base case: does it catch the smallest input you’ll ever pass?

Bug: Fibonacci fib(45) takes forever. What it means: Exponential redundant work without memoization. Fix: Add a cache as in §7.8, or rewrite iteratively.

Bug: Recursive function returns the wrong value but no error. What it means: Either the base case returns the wrong thing, or the recursive case combines the recursive result incorrectly. Fix: Trace by hand with the smallest non-trivial input. factorial(2) should be 2, factorial(3) should be 6. If factorial(2) is wrong, the bug is in the base case or in n * factorial(n-1). Print intermediate values.

Bug: Directory walker visits the same file twice. What it means: Symbolic links or an accidental cycle. Or you recursed on the file instead of the directory. Fix: Track visited paths in a Set<Path> and skip duplicates. For symlinks specifically, use Files.walk(root, FileVisitOption.NOFOLLOW_LINKS) — though links are normally not followed by default with Files.newDirectoryStream.

Bug: Recursive function uses a shared mutable state and produces strange results. What it means: A field or static variable is being modified across recursive calls in a way you didn’t intend. Fix: Pass state as a parameter (the “accumulator” pattern), not via mutable state shared across calls. Recursion is cleanest when each call is a pure transformation of its inputs.

Bug: ClassCastException when walking a nested Map<String, Object>. What it means: The pattern-match was wrong; the value was, for example, a List, not a Map. Fix: Handle all the shapes you actually have. A general nested-data walker often needs to handle Map, List, and scalar types separately.

7.11 — Reps

Open the exercises for the full set. Sample:

Rep 1. Write factorial recursively. Hand-trace factorial(5). Confirm the trace matches the program output.

Rep 4. Write the recursive gcd. Test on five pairs.

Rep 7. Write printNested for a nested map. Build a config map of your own.

Rep 9. Memoize Fibonacci. Time before and after.

Full set in the exercises.

7.12 — This Week’s Project: Three Recursive Problems

You’re ready for Project 7: Three Recursive Problems, in Project 7.

Three classic problems, one recursive solution each:

1. Greatest common divisor.
2. A recursive directory walker that lists every .java file under a given root.
3. A pretty-printer for a nested Map<String, Object>.

Then, for Medium: memoize a Fibonacci or coin-change problem and benchmark the difference. For Hard: convert one of the three problems to pure iteration and write a short essay on which reads more clearly and why.

7.13 — A Seed for Coding 3

Coding 3 will introduce trees and graphs as first-class data structures, with the algorithms that walk them: depth-first search, breadth-first search, binary search trees, balanced trees, the works. Every one of those algorithms is recursive (or iteratively walks a stack/queue, which is the same idea with explicit bookkeeping). The mental fluency you built this week is the foundation that will make those topics feel natural rather than alien.

For now, we are using the patterns — walking nested data, walking the file system — without yet calling them “tree traversals.” But you have already, this week, walked a tree. The data was the directory structure; the algorithm was recursive descent. Next year, when the formal vocabulary arrives, your hands will already know the move.

7.14 — Common Bugs (continued, for the project)

(Already covered in §7.10. Tape that list near your screen for Project 7.)

7.15 — Coach’s Final Word for Week 7

Recursion is one of the small handful of ideas in computer science that genuinely changes how you see problems. Before recursion, the only repetition you had was a loop. After recursion, you can solve any self-similar problem with a function whose body looks startlingly like the problem’s own definition.

For the apologetic frame: the part contains the whole. In the body of Christ, each member is whole in its particular calling and partial within the larger body. In the gospel, each soul is whole in its singular dignity and part of the larger people. The mathematical idea and the theological idea share a structure — not by coincidence, but because reality has the shape it has, and we discover that shape both ways.

The midterm is next week. Chapter 8 is collections, generics, and the cumulative review. Show up rested. Trust the reps.

See you on Monday.

Up next: Read the exercises and run every rep. Then open Project 7 and solve the three problems. After that, Chapter 8 — Collections, Generics, and Midterm Review.