Recursion and backtracking

A recursive function solves a problem by calling itself on a smaller version of the same problem. It needs two parts: a base case small enough to answer directly, and a recursive case that makes the problem smaller and combines the smaller answers. If either is missing or wrong, the function never stops, or stops with the wrong answer. Interviewers use recursion to test whether you can break a problem into smaller copies of itself, and backtracking (recursion that tries choices) to test whether you can explore every option without missing or repeating one.

Trust the smaller call

The hardest habit to build is not tracing every call in your head. Assume the call on the smaller input already works, and only ask: "given that answer, how do I build mine?" For x to the power n (n is the exponent, the number of times x is multiplied), the smaller problem is x to the power n / 2. Square it, and multiply by x once more if n is odd. For 2 to the power 10: 2⁵ = 32, and 32 × 32 = 1024. The exponent halves each time, so even n = 10¹⁸ needs only about 60 calls.

Backtracking: choose, explore, undo

Backtracking explores choices. At each step you make one choice, call the function again to handle the rest, then undo the choice and try the next one. Subsets, permutations, combination sum, balanced brackets (every opening bracket closed in the right order) and word search all follow this template:

solve(state):
    if state is complete: record a copy of it, return
    for each choice that is still allowed:
        apply the choice
        solve(state)
        undo the choice

For subsets, the choice at each position is "leave the value out" or "take it". The choices form a tree, and every leaf (an end point of the tree) is one subset:

The program below shows the fast power function and the subsets template on 1, 2, 3, which adds a third level to the tree and gives 8 subsets.

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

public class Main {
    static long power(long x, int n) {
        if (n == 0) {
            return 1;                              // base case
        }
        long half = power(x, n / 2);               // a smaller copy of the problem
        return n % 2 == 0 ? half * half : half * half * x;
    }

    static void subsets(int[] nums, int i, List<Integer> current, List<List<Integer>> out) {
        if (i == nums.length) {
            out.add(new ArrayList<>(current));     // save a copy
            return;
        }
        subsets(nums, i + 1, current, out);        // leave nums[i] out
        current.add(nums[i]);                      // choose
        subsets(nums, i + 1, current, out);        // explore
        current.remove(current.size() - 1);        // undo the choice
    }

    public static void main(String[] args) {
        System.out.println(power(2, 10));
        List<List<Integer>> out = new ArrayList<>();
        subsets(new int[] { 1, 2, 3 }, 0, new ArrayList<>(), out);
        System.out.println(out);
    }
}

1024
[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

def power(x, n):
    if n == 0:
        return 1                       # base case
    half = power(x, n // 2)            # a smaller copy of the problem
    return half * half if n % 2 == 0 else half * half * x


def subsets(nums, i, current, out):
    if i == len(nums):
        out.append(current[:])         # save a copy
        return
    subsets(nums, i + 1, current, out)     # leave nums[i] out
    current.append(nums[i])                # choose
    subsets(nums, i + 1, current, out)     # explore
    current.pop()                          # undo the choice


print(power(2, 10))
out = []
subsets([1, 2, 3], 0, [], out)
print(out)

1024
[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

Pruning

The tree of choices grows fast: 2ⁿ subsets, n! orderings (n! is "n factorial": n × (n - 1) × ... × 1, so 3! = 6). Pruning means refusing a choice as soon as you know it cannot lead to a valid answer. In combination sum, sort the candidates and stop the loop when a candidate is larger than what remains. When generating balanced brackets, never add a closing bracket that has nothing to close. In word search, stop a path the moment a letter does not match. Good pruning is often the difference between a solution that finishes and one that times out.

The call stack and its limits

Every call that has not returned yet keeps a frame (a stored record of that call) on the call stack. Deep recursion can run out of room: Java throws StackOverflowError, and Python raises RecursionError once more than 1,000 calls are nested (the default limit, which sys.setrecursionlimit can change). A recursive walk over a linked list or a very unbalanced tree is as deep as the data is long. When depth can reach tens of thousands, write the same logic as a loop with your own stack.

How to answer in an interview

State the base case first, then the recursive case in one sentence ("the subsets of the rest, once without this value and once with it"). For backtracking, say what one choice is and how you undo it. Draw the top of the choice tree for a tiny input, and give the cost by counting answers times work per answer: O(n × 2ⁿ) for subsets, O(n × n!) for permutations.

Common mistakes

• Saving the working list instead of a copy, so every saved answer changes with it and they all end up the same.
• Forgetting to undo: a "used" mark or a visited cell that is not cleared blocks later paths.
• Duplicate answers in combination problems; start the loop at the current position, never at 0.
• Solving the same smaller problem again and again, as in plain recursive Fibonacci. Store each answer once it is known (memoisation), the first step towards dynamic programming (see Further problems).

Recap

Write the base case, trust the smaller call, and for backtracking follow choose, explore, undo. Prune early, save copies, and switch to a loop with your own stack when the depth can get large.