Recursion and Backtracking

Every divide and conquer algorithm, every dynamic programming solution, and every tree traversal rests on recursion. It is the foundational control structure of algorithm design. Backtracking extends recursion into a systematic framework for exploring all possible solutions while pruning dead ends early.

This chapter starts with recursion fundamentals — the mechanics that make recursive algorithms work — and then builds up to the full backtracking template that you will use to solve permutations, combinations, subsets, Sudoku, and constraint satisfaction problems.

Recursion Fundamentals

Base Case and Recursive Case

Every recursive function has two parts:

• Base case: the termination condition. When the input is small enough, return a result directly without further recursion. Without a base case, recursion runs forever (or until the stack overflows).
• Recursive case: the function calls itself with a smaller version of the problem. Each recursive call must make progress toward the base case.

long factorial(int n) {
    if (n <= 1) return 1;              // base case
    return n * factorial(n - 1);       // recursive case
}

The Call Stack

Each recursive call pushes a stack frame onto the call stack, containing the function’s local variables, parameters, and return address. When the base case returns, frames pop off the stack in reverse order.

For factorial(4):

factorial(4) → pushes frame, calls factorial(3)
  factorial(3) → pushes frame, calls factorial(2)
    factorial(2) → pushes frame, calls factorial(1)
      factorial(1) → base case, returns 1
    returns 2 * 1 = 2
  returns 3 * 2 = 6
returns 4 * 6 = 24

The call stack has a finite size. Deep recursion (thousands of levels) causes StackOverflowError in Java. The default stack size is around 512KB to 1MB, supporting roughly 5,000–15,000 frames depending on frame size.

Tail Recursion

A recursive call is tail recursive if it is the last operation before the function returns — no multiplication, no addition, no further processing after the call returns.

// NOT tail recursive — multiplication happens after the recursive call
long factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

// Tail recursive — the recursive call is the final operation
long factorialTail(int n, long accumulator) {
    if (n <= 1) return accumulator;
    return factorialTail(n - 1, n * accumulator);
}

Some languages (Scheme, Haskell, Scala) optimize tail recursion into a loop, eliminating stack growth. The JVM does not perform tail call optimization as of Java 25. This means tail recursion in Java still consumes stack frames. For deep recursion in Java, convert to an iterative solution with an explicit stack.

Thinking Recursively

The key insight is trust: assume the recursive function works correctly for all smaller inputs, then define how the current input relates to those smaller results.

Step 1: Define what f(n) returns. Be precise. Step 2: Define how f(n) relates to f(smaller input). Step 3: Define the base case — the smallest input for which you can compute the answer directly.

Example — Power Function: compute $x^n$.

double power(double x, long n) {
    if (n == 0) return 1.0;             // base case
    if (n < 0) return 1.0 / power(x, -n);

    double half = power(x, n / 2);     // trust this works
    if (n % 2 == 0) {
        return half * half;
    } else {
        return half * half * x;
    }
}

You trust that power(x, n/2) returns the correct value, then you use it to build the answer for n. That’s the entire reasoning process.

The Backtracking Template

Backtracking is recursion with a twist: you make a tentative choice, explore the consequences, and then undo the choice to try alternatives. The undo step is what distinguishes backtracking from plain recursion.

Here is the universal template:

void backtrack(state, choices):
    if isGoal(state):
        addToResults(state)
        return

    for choice in choices:
        if isValid(choice, state):
            make(choice)                // modify state
            backtrack(state, next_choices)
            undo(choice)                // restore state

The three-step cycle at the core:

1. Choose: select an option and modify the current state
2. Explore: recurse with the updated state
3. Unchoose: undo the modification, restoring the state to what it was before

The “unchoose” step is critical. Without it, each recursive branch would inherit modifications from all previous branches, producing incorrect results.

Classic Backtracking Problems

1. Subsets (Power Set)

Problem: generate all $2^n$ subsets of a set of $n$ distinct elements.

Approach: for each element, you have two choices — include it or exclude it. This creates a binary decision tree of depth $n$.

List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrackSubsets(nums, 0, new ArrayList<>(), result);
    return result;
}

void backtrackSubsets(int[] nums, int start, List<Integer> current,
                      List<List<Integer>> result) {
    result.add(new ArrayList<>(current)); // every node is a valid subset

    for (int i = start; i < nums.length; i++) {
        current.add(nums[i]);                          // choose
        backtrackSubsets(nums, i + 1, current, result); // explore
        current.removeLast();                           // unchoose
    }
}

Note the new ArrayList<>(current) — you must copy the current state when saving it, because current is mutable and will be modified by future choose/unchoose steps.

Time complexity: $O(n \cdot 2^n)$ — there are $2^n$ subsets, and copying each takes $O(n)$.

2. Permutations

Problem: generate all $n!$ permutations of $n$ distinct elements.

Approach: at each position, try every unused element. Use a boolean array to track which elements are in use.

List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    boolean[] used = new boolean[nums.length];
    backtrackPermute(nums, used, new ArrayList<>(), result);
    return result;
}

void backtrackPermute(int[] nums, boolean[] used, List<Integer> current,
                      List<List<Integer>> result) {
    if (current.size() == nums.length) {
        result.add(new ArrayList<>(current));
        return;
    }

    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;

        used[i] = true;                                     // choose
        current.add(nums[i]);
        backtrackPermute(nums, used, current, result);       // explore
        current.removeLast();                                // unchoose
        used[i] = false;
    }
}

Time complexity: $O(n \cdot n!)$ — $n!$ permutations, each taking $O(n)$ to copy.

3. Combinations

Problem: choose $k$ elements from $n$ (order doesn’t matter).

Approach: like subsets, but with a size constraint. Stop adding elements once the current list has $k$ elements.

List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> result = new ArrayList<>();
    backtrackCombine(n, k, 1, new ArrayList<>(), result);
    return result;
}

void backtrackCombine(int n, int k, int start, List<Integer> current,
                      List<List<Integer>> result) {
    if (current.size() == k) {
        result.add(new ArrayList<>(current));
        return;
    }

    // Pruning: stop if not enough elements remaining
    int remaining = n - start + 1;
    int needed = k - current.size();
    if (remaining < needed) return;

    for (int i = start; i <= n; i++) {
        current.add(i);                                   // choose
        backtrackCombine(n, k, i + 1, current, result);    // explore
        current.removeLast();                              // unchoose
    }
}

The pruning check remaining < needed cuts off branches where it is impossible to reach $k$ elements. This is a significant optimization in practice.

4. Combination Sum

Problem: find all unique combinations where candidate numbers sum to a target. Each number can be used unlimited times.

List<List<Integer>> combinationSum(int[] candidates, int target) {
    Arrays.sort(candidates); // enables pruning
    List<List<Integer>> result = new ArrayList<>();
    backtrackCombSum(candidates, target, 0, new ArrayList<>(), result);
    return result;
}

void backtrackCombSum(int[] candidates, int remaining, int start,
                      List<Integer> current, List<List<Integer>> result) {
    if (remaining == 0) {
        result.add(new ArrayList<>(current));
        return;
    }

    for (int i = start; i < candidates.length; i++) {
        if (candidates[i] > remaining) break; // pruning: sorted, so all after are too large

        current.add(candidates[i]);                                 // choose
        backtrackCombSum(candidates, remaining - candidates[i],
                         i, current, result);                        // explore (i, not i+1: reuse allowed)
        current.removeLast();                                        // unchoose
    }
}

Key details: passing i (not i + 1) to allow reuse of the same element. Sorting enables the break pruning — once a candidate exceeds the remaining target, all subsequent candidates are even larger.

5. Sudoku Solver

Problem: fill a 9×9 grid so that each row, column, and 3×3 box contains the digits 1–9 exactly once.

Approach: find the first empty cell, try digits 1–9, backtrack on constraint violations.

boolean solveSudoku(char[][] board) {
    boolean[][] rowUsed = new boolean[9][10];
    boolean[][] colUsed = new boolean[9][10];
    boolean[][] boxUsed = new boolean[9][10];

    // Initialize constraint arrays from existing board
    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) {
            if (board[r][c] != '.') {
                int num = board[r][c] - '0';
                int box = (r / 3) * 3 + c / 3;
                rowUsed[r][num] = true;
                colUsed[c][num] = true;
                boxUsed[box][num] = true;
            }
        }
    }

    return solve(board, rowUsed, colUsed, boxUsed);
}

boolean solve(char[][] board, boolean[][] rowUsed,
              boolean[][] colUsed, boolean[][] boxUsed) {
    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) {
            if (board[r][c] != '.') continue;

            int box = (r / 3) * 3 + c / 3;

            for (int num = 1; num <= 9; num++) {
                if (rowUsed[r][num] || colUsed[c][num]
                        || boxUsed[box][num]) {
                    continue; // constraint violation
                }

                // Choose
                board[r][c] = (char) ('0' + num);
                rowUsed[r][num] = true;
                colUsed[c][num] = true;
                boxUsed[box][num] = true;

                // Explore
                if (solve(board, rowUsed, colUsed, boxUsed)) {
                    return true;
                }

                // Unchoose
                board[r][c] = '.';
                rowUsed[r][num] = false;
                colUsed[c][num] = false;
                boxUsed[box][num] = false;
            }

            return false; // no valid digit for this cell → backtrack
        }
    }
    return true; // all cells filled
}

The boolean[9][10] arrays provide $O(1)$ constraint checking. Without them, you’d scan the entire row, column, and box for each candidate digit — $O(n)$ per check, which compounds across the recursion tree.

The return false after the digit loop is a crucial line: it means “we tried all digits for this cell and none worked, so backtrack.” This is the mechanism that triggers the unchoose step in the calling frame.

6. Generate Parentheses

Problem: generate all valid combinations of $n$ pairs of parentheses.

Approach: track the count of open and close parentheses. Constraints: at any point, closes must not exceed opens, and opens must not exceed $n$.

List<String> generateParenthesis(int n) {
    List<String> result = new ArrayList<>();
    backtrackParens(n, 0, 0, new StringBuilder(), result);
    return result;
}

void backtrackParens(int n, int open, int close,
                     StringBuilder current, List<String> result) {
    if (current.length() == 2 * n) {
        result.add(current.toString());
        return;
    }

    if (open < n) {
        current.append('(');                                   // choose
        backtrackParens(n, open + 1, close, current, result);   // explore
        current.deleteCharAt(current.length() - 1);             // unchoose
    }

    if (close < open) {
        current.append(')');                                   // choose
        backtrackParens(n, open, close + 1, current, result);   // explore
        current.deleteCharAt(current.length() - 1);             // unchoose
    }
}

The pruning is built into the if conditions: open < n ensures you don’t use more than $n$ open parentheses, and close < open ensures the string stays valid at every step. This cuts the search space from $2^{2n}$ (all binary strings of length $2n$) to the $n$-th Catalan number $\frac{1}{n+1}\binom{2n}{n}$.

Pruning Strategies

Pruning is what makes backtracking practical. Without pruning, backtracking is brute force. With good pruning, it solves problems that appear intractable.

Constraint-based Pruning

Skip choices that violate known constraints before recursing. This is the most common form — the Sudoku solver’s constraint checks are a prime example.

Bound-based Pruning (Branch and Bound)

Compute an upper (or lower) bound on the best solution achievable from the current state. If this bound is worse than the best solution found so far, prune the entire subtree. This is particularly effective for optimization problems.

void branchAndBound(state):
    if bound(state) <= bestSoFar:
        return  // prune: can't improve
    if isComplete(state):
        bestSoFar = max(bestSoFar, value(state))
        return
    for choice in choices:
        make(choice)
        branchAndBound(state)
        undo(choice)

Symmetry-based Pruning

If the problem has symmetries (rotations, reflections, equivalent orderings), avoid exploring symmetric configurations. For example, in the N-Queens problem, placing the first queen only in the left half of the first row and mirroring results cuts the search space in half.

Recursion vs Iteration

Any recursive algorithm can be converted to an iterative one using an explicit stack. The call stack is a stack — replace it with your own Stack<State> and you get the same behavior without risking overflow.

When to convert:

• Deep recursion: when the recursion depth exceeds the JVM stack limit (several thousand frames). Tree traversals on skewed trees, for example.
• Performance: eliminating recursion overhead saves function call setup/teardown. For hot loops, this matters.
• Tail recursion: since the JVM doesn’t optimize tail calls, converting tail recursion to a while loop is always beneficial.

When to keep recursion:

• Tree and graph problems: recursive DFS, tree traversals, and backtracking are dramatically easier to read and write recursively.
• Divide and conquer: the recursive structure maps directly to the problem’s structure. Iterative D&C is awkward and error-prone.
• Interview clarity: recursive solutions are faster to write, easier to reason about, and more likely to be bug-free under time pressure.

Complexity of Backtracking

Backtracking algorithms typically have exponential or factorial time complexity:

Problem	Time Complexity	Space Complexity
Subsets	$O(n \cdot 2^n)$	$O(n)$ recursion depth
Permutations	$O(n \cdot n!)$	$O(n)$ recursion depth
Combinations C(n,k)	$O(k \cdot \binom{n}{k})$	$O(k)$ recursion depth
Sudoku (worst case)	$O(9^{81})$	$O(81)$ recursion depth
N-Queens	$O(n!)$	$O(n)$ recursion depth

Pruning reduces the constant factors and eliminates large portions of the search tree, but it does not change the worst-case asymptotic class. In practice, well-pruned backtracking runs orders of magnitude faster than the worst case.

For Sudoku, the theoretical worst case is $O(9^{81})$, but constraint pruning reduces the actual number of nodes explored to a few thousand for most puzzles.

Interviewer Tips

1. Draw the recursion tree. Before coding, sketch a few levels of the decision tree on the whiteboard. This clarifies the choose/explore/unchoose structure and helps you identify the base case and pruning opportunities. Interviewers love visual explanations.

2. State the template explicitly. Say “I’m using the backtracking template: choose, explore, unchoose.” This signals that you have a systematic approach, not ad hoc coding.

3. Make a defensive copy. When adding the current state to results, always copy it (new ArrayList<>(current)). Mutable state is shared across recursive branches — forgetting to copy is one of the most common backtracking bugs.

4. Prune early. Mention pruning opportunities even if the basic solution doesn’t need them. “We could add a bound check here to cut branches early” shows optimization awareness.

5. Watch for off-by-one in the start index. For subsets and combinations, the next recursive call uses start = i + 1 (not start + 1). For combination sum with reuse, it uses start = i. Getting this wrong produces duplicates or missing combinations.

6. Know the pattern recognition. “Generate all…” = subsets/permutations/combinations backtracking. “Find if a valid configuration exists…” = constraint satisfaction backtracking. “Optimize over all configurations…” = backtracking + bound pruning (or DP if subproblems overlap).