Recursion & Backtracking

Interviewer: “Generate all subsets of this array.” You reach for nested loops and realize you’d need a loop per element — but the array length isn’t fixed. Every “generate ALL the things” problem has this shape, and loops can’t touch it. Recursion can, and backtracking is recursion with an undo button.

The Goal

By the end of this module you can:

• Explain recursion as the call stack doing your bookkeeping — no magic, just frames
• Write any recursive function from the two non-negotiables: a base case and a smaller input
• Read recursive code by trusting the function, instead of hand-tracing five levels deep
• Estimate recursive cost from the recursion tree — branches to the power of depth
• Implement the choose/explore/unchoose backtracking template in Java and prune dead branches early
• Recognize “generate all X” and “can you place/partition” as backtracking signals in 30 seconds

The Lesson

Recursion is not magic — it’s the stack you already know

In how-java-runs you learned that every method call gets a frame on the call stack — its own copy of parameters and locals — and the frame pops when the method returns. That’s the whole secret. A recursive function is just a method that calls itself, and the JVM stacks up one frame per call, each with its own n, exactly as it would for any other method. Nothing special happens because the method’s name matches.

public class Sum {
    static int sumTo(int n) {
        if (n == 0) return 0;          // base case
        return n + sumTo(n - 1);       // smaller input
    }

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

sumTo(4) pushes a frame, which pushes a frame for sumTo(3), down to sumTo(0) — which returns 0 without recursing, and the stack unwinds: 0, then 1, 3, 6, 10. You manually pushed and popped a Deque in the stacks module; recursion is the JVM doing that push/pop for you, with the bookmark of “where was I?” stored free of charge in each frame.

The two non-negotiables

Every correct recursive function has exactly two things. Miss either and it doesn’t terminate:

“Smaller” means measurably closer to the base case: n - 1, index + 1 toward the array’s end, a subtree instead of the tree. If you can’t point at what shrinks, the function is broken — no exceptions to this rule exist.

And when it doesn’t terminate, Java tells you loudly: StackOverflowError. The stack region is finite (around 512KB–1MB by default), which fits roughly 10,000–20,000 frames. A recursion that’s correct but very deep — say sumTo(100_000) — dies the same way as an infinite one. That’s a real design constraint: recursion depth in Java must stay in the low thousands, or you convert to a loop or an explicit stack.

How to READ recursion — trust the function

The number one beginner mistake: trying to trace every call by hand, five levels deep, drowning in frames. Professionals never do that. The reading technique is the leap of faith:

1. Check the base case is right.
2. Assume the recursive call works. sumTo(n - 1) correctly returns the sum to n-1. Done, assumed, don’t trace it.
3. Check the current level: if sumTo(n - 1) is correct, is n + sumTo(n - 1) the right answer for n?
4. Check every call shrinks the input.

If all four hold, the function is correct — that’s induction, the same logic mathematicians use, and it scales to any depth without tracing. You verify ONE level and the base; the stack handles the rest. Write recursion the same way: write the base case, then write f(n) in terms of f(smaller) as if f(smaller) already works.

The recursion tree — your cost model

One call that makes two calls, each making two more, is a tree. The tree is how you price recursion: cost ≈ branches^depth. The textbook horror story is naive Fibonacci:

static long fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);   // two branches per call
}

flowchart TD
    A["fib 5"] --> B["fib 4"]
    A --> C["fib 3"]
    B --> D["fib 3"]
    B --> E["fib 2"]
    C --> F["fib 2"]
    C --> G["fib 1"]
    D --> H["fib 2"]
    D --> I["fib 1"]

Two branches, depth n: roughly O(2^n) calls. fib(50) is over a quadrillion calls — your laptop will not finish before your interview slot ends. Look at the tree again: fib 3 is computed twice, fib 2 three times — entire identical subtrees, recomputed from scratch. Hold that thought; it’s the single observation that dp-intro is built on. For now, the takeaway is the pricing skill: count the branches, count the depth, multiply. One branch (like sumTo) is O(n). Two branches and depth n is O(2^n) unless something prunes or remembers.

Backtracking = recursion + undo

Now the headline act. Backtracking explores every possible sequence of choices by walking down one path, and when it returns, undoing the choice so the shared state is clean for the next path. The template — memorize this shape:

void backtrack(State state, Choices remaining) {
    if (nothing left to choose) {       // base case
        record or print the result;
        return;
    }
    for (each available choice) {
        make the choice;                // CHOOSE
        backtrack(updated state);       // EXPLORE
        undo the choice;                // UNCHOOSE - the part everyone forgets
    }
}

Choose, explore, unchoose. The unchoose step is what makes one shared path list reusable across all branches instead of copying it at every level. Here it is real, generating all subsets of {1, 2, 3} — every element faces one binary choice, in or out:

import java.util.ArrayList;
import java.util.List;

public class Subsets {
    public static void main(String[] args) {
        explore(new int[]{1, 2, 3}, 0, new ArrayList<>());
    }

    static void explore(int[] nums, int index, List<Integer> path) {
        if (index == nums.length) {            // no choices left
            System.out.println(path);
            return;
        }
        // Choice A: leave nums[index] out
        explore(nums, index + 1, path);

        // Choice B: take nums[index]
        path.add(nums[index]);                 // choose
        explore(nums, index + 1, path);        // explore
        path.remove(path.size() - 1);          // unchoose
    }
}

Eight lines of logic, eight subsets printed: [], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]. Two choices per element, n elements: 2^n subsets, O(2^n) time — and that’s optimal, because the output itself has 2^n entries. You can’t beat the size of your own answer.

The same template, re-skinned, solves the other classics:

• Permutations: instead of in/out, the choice at each level is “which unused element goes in this position?” — loop over all elements, skip used ones, choose/explore/unchoose. n options then n-1 then n-2: O(n!) results.
• N-Queens: the choice at row r is “which column gets the queen?” Choose a column, recurse to row r+1, unchoose. Base case: placed all n rows.

Pruning — bail before wasting the work

Raw backtracking visits every branch. Pruning kills a branch the moment the partial answer is already invalid — why explore a subtree that cannot contain a solution? In N-Queens, you don’t place a queen on an attacked square and then check; you skip attacked columns before recursing. If a partial sum already exceeds the target in a combination-sum problem, return immediately — every deeper node only adds more.

if (currentSum > target) return;   // this entire subtree is dead - skip it

One line, and trees that would take minutes collapse to milliseconds. Pruning doesn’t change the worst-case Big-O, but in practice it’s the difference between “finishes instantly” and “still running.” Every serious backtracking solution prunes.

See It Move

Watch fib(5) unfold as a live call tree — leave the memo toggle OFF for this whole module; what memo does to this tree is module 11’s reveal, don’t spoil it.

Step through it and notice:

• Calls go deep before wide — fib 5 to fib 4 to fib 3 down to a base case, then back up one level, then down the next branch. That’s the call stack pushing and popping, the order DFS gave you in trees-bfs-dfs.
• Point at the duplicates: fib 3 appears twice, fib 2 three times — identical subtrees, fully recomputed each time. The waste is structural, not a bug.
• A node only returns after both its children return — watch a parent wait. That waiting is a live frame holding its bookmark on the stack.
• Count the total calls for fib(5), then imagine fib(50). The tree roughly doubles per +1 of n. That’s what O(2^n) feels like.

Spot The Pattern

Where It Runs In Real Life

File-tree walking. “Process every file under this folder” is recursion verbatim: handle the folder’s files, recurse into each subfolder. The base case is a folder with no subfolders. Every backup tool, search indexer, and du-style disk analyzer is this five-line function.

JSON parsing — recursive descent. JSON is self-similar: an object contains values, and a value can be another object. Parsers like the ones inside Jackson and Gson are recursive descent parsers — parseValue calls parseObject calls parseValue. The grammar is recursive, so the cleanest parser is too.

Regex engines. Backtracking is so central to regex matching that it’s in the official terminology: when a partial match fails, the engine backtracks and tries another way to match. It’s also why a malicious pattern can take exponential time — catastrophic backtracking is a real production outage class (a regex once took down Cloudflare globally for half an hour in 2019).

Sudoku and constraint solvers. Try a digit in a cell, recurse; on contradiction, erase it and try the next — choose/explore/unchoose with pruning, character for character the template above. Industrial constraint solvers for timetabling and logistics are this idea hardened.

Dependency resolution. When Maven or npm picks package versions, choosing one version constrains everything downstream; a dead end means backing up and trying another version. Compilers run the same shape: source code parses into an AST — a recursive structure — and every later phase recursively walks it.

Build This

You’re building a subset explorer, then breaking it twice to feel exactly why each template line exists.

1. Create SubsetExplorer.java and type all of it:

import java.util.ArrayList;
import java.util.List;

public class SubsetExplorer {
    static int calls = 0;

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        explore(nums, 0, new ArrayList<>());
        System.out.println("Total calls: " + calls);
    }

    static void explore(int[] nums, int index, List<Integer> path) {
        calls++;
        if (index == nums.length) {           // base case: every element decided
            System.out.println(path);
            return;
        }
        // Choice A: leave nums[index] out
        explore(nums, index + 1, path);

        // Choice B: take nums[index]
        path.add(nums[index]);                // choose
        explore(nums, index + 1, path);       // explore
        path.remove(path.size() - 1);         // unchoose
    }
}

2. Compile and run. Confirm all 8 subsets print and note the call count. Grow nums to 4, then 5 elements — watch the count roughly double each time. You are watching O(2^n) happen.

3. Break it — kill the unchoose. Comment out the path.remove(...) line. Run. Subsets now bleed into each other — elements stick around in branches that never chose them, because all calls share one path list. No exception, just corrupted output. That’s why unchoose is non-negotiable. Fix it back.

4. Break it — kill the progress. Change Choice A’s call to explore(nums, index, path); — same index, input no longer shrinks. Run, and meet StackOverflowError. Read the stack trace (how-java-runs style): the same line repeats thousands of times. That’s what infinite descent looks like — and roughly how many frames Java tolerated before dying. Fix it back.

5. Extend it — prune. Add a parameter int budget and a guard at the top: if the sum of path exceeds budget, return immediately, before recursing. Call it with budget 4 and confirm subsets like [2, 3] and [1, 2, 3] never even get explored. Print the call count with and without the guard — that delta is pruning, measured.

6. Extend it — permutations. Write permute(int[] nums, List<Integer> path, boolean[] used): base case is path.size() == nums.length; otherwise loop over all elements, skip used ones, and choose (add + mark used) / explore / unchoose (remove + unmark). All 6 orderings of {1, 2, 3} should print. Same template, different choice set.

Problems To Solve

For the full drill list, work through the Backtracking section of neetcode.io’s roadmap.

The rule: solve until you can write the choose/explore/unchoose template from memory. If you’re stuck 25 minutes, read the approach, close it, and re-solve from scratch.

Check Yourself

1. What are the two non-negotiables of every recursive function, and what error do you get when one is missing?
2. Where does the “where was I?” bookkeeping live when a function recurses, and what does each frame hold?
3. What is the leap-of-faith reading technique, and why is it valid?
4. How do you estimate the cost of a recursive function from its tree? Apply it to naive fib.
5. Roughly how many stack frames does Java tolerate, and what does that mean for deep recursion design?
6. Recite the three steps of the backtracking template. Which one makes a shared path list safe across branches?
7. What is pruning, and does it change worst-case Big-O?
8. “Count the number of ways to do X” versus “list every way to do X” — why might these deserve different techniques?

Explain it out loud: Explain choose/explore/unchoose to an empty chair using the subsets code — specifically, what goes wrong when the unchoose line is deleted and WHY, in terms of the one shared list and the call stack. If you can’t explain the corruption without running the code, redo Build This step 3.

Still Unclear?

Copy-paste any of these into Claude — they deepen understanding without doing the work for you:

I am learning recursion in Java. Give me a recursive function with a subtle bug
(wrong base case, or input that does not shrink, or a missing unchoose) and let
me find it by reading, not running. Then another. Increase difficulty each time
and tell me which bug family I am slowest at spotting.

Quiz me on recursion tree cost: describe 5 recursive functions in words (how many
recursive calls each makes, what shrinks) and make me estimate the Big-O of each
from branches and depth before you reveal it. No code, mental math only.

I know the subsets backtracking template. Walk me through adapting it to
permutations step by step, but make ME propose each change first - what is the
choice at each level, what is the base case, what must unchoose restore - and
correct my reasoning before showing anything.

Why AI Can’t Do This For You

AI writes a perfect N-Queens solver in two seconds — it has memorized a thousand of them. But “generate all valid X” almost never arrives labeled. It arrives as “show every way the splitwise group can settle up” or “list all rollout orders that respect these service dependencies” — and the engineer who maps that sentence to choose/explore/unchoose, picks the right choice set, and knows the output is exponential before writing code is doing the part no prompt does. Recognition under vague wording is the whole game.

There’s a second layer: recursion is the rare topic where reading skill beats writing skill. When a recursive function misbehaves in production — a stack overflow on deep folder structures, a regex pinned at 100% CPU — AI can’t feel which frame is yours or what your data’s depth looks like. The person who can read a 4,000-line recursive stack trace and say “the input isn’t shrinking when the list has duplicates” closes the incident. That’s leap-of-faith reading plus tree-cost instinct, and you only get those from reps.

Module done? Add it to today’s tracker