Recursion and backtracking in Rust

You are in a maze. At the first fork, you take the left path. It leads to a dead end. You do not give up and you do not start over. You walk back to the fork, and take the right path instead. At the next fork, you do the same thing: pick a road, and if it fails, return and pick another.

That habit is backtracking: try a choice, see where it leads, and if it goes wrong, undo it and try the next choice. It is how you solve a puzzle that has too many possibilities to see at once, such as every way to seat guests, or every set of items that fit in a bag.

Backtracking is built on recursion, which is a function that solves a big problem by calling itself on a smaller one. Think of a set of nesting dolls. To find the smallest doll, open the doll, and ask the same question of the doll inside.

Reach for recursion when a problem is made of smaller copies of itself: a folder with folders inside, a tree (lesson 7), or "choose, then solve the rest". Reach for backtracking when you must list or count all the ways to do something.

Start with plain recursion, and a small example. The factorial of 4, written 4!, is 4 × 3 × 2 × 1. Notice that 4! is just 4 × 3!, and 3! is 3 × 2!. Each answer asks for a smaller copy of the same question.

Here is what the computer does. It calls factorial(4), which needs factorial(3) before it can finish. So it pauses the first job and starts the second. That one needs factorial(2), so it pauses and starts a third. Then factorial(1), which is simple: the answer is 1, with no more asking. Now the pile unwinds. factorial(2) gets 1 and finishes with 2. factorial(3) finishes with 6. factorial(4) finishes with 24.

The pile of paused jobs is the call stack. It is a stack in exactly the sense of lesson 4: the newest job is on top, and only the top job runs. Each paused job keeps its own copy of its variables, like its own page of rough work.

Every recursive function needs two things.

• A base case: a question so simple that it is answered directly, with no more calls. factorial(1) was one. Without it, the calls never stop.
• A smaller step: each call must move closer to the base case. Here the number drops by one each time.

Remember: a recursive function needs a base case that stops, and a step that gets closer to it.

Now backtracking. Take the items 1, 2 and 3, and list every way to choose some of them. The picture is the answer. At each item, there is a fork with two roads: skip it, or take it. Three items means three forks, so 2 × 2 × 2 = 8 finished choices. These are the subsets: nothing, just 1, just 2, and so on up to all three.

The search walks the tree from the top. It goes left everywhere first and reaches the empty subset. Then it steps back up one fork, takes the other road, and reaches {3}. The key is the step back. When you take an item, you add it to the list you are building. Before you try the next road, you must undo that, or the leftover item would sneak into later answers.

The pattern has three beats, and you will see it in every backtracking problem: choose, explore, un-choose.

Start with plain recursion. These two are the smallest examples.

/// 5! is 5 * 4 * 3 * 2 * 1. A function that solves its job by asking a
/// smaller copy of itself.
pub fn factorial(n: u64) -> u64 {
    // Base case: the answer is known, so nothing more is asked.
    if n <= 1 {
        return 1;
    }
    n * factorial(n - 1)
}

The line if n <= 1 is the base case. After it, n * factorial(n - 1) is the smaller step. The answer to factorial(20) is the biggest that fits in a u64, so the demo stays small.

/// Adds up a slice by taking off the first item and asking for the rest.
pub fn sum_list(nums: &[i32]) -> i32 {
    match nums.split_first() {
        None => 0, // an empty list adds up to nothing
        Some((first, rest)) => first + sum_list(rest),
    }
}

This one adds a slice. split_first takes the first item off and hands back the rest, or None for an empty slice. The base case is the empty list, which sums to 0. Otherwise, the answer is the first item plus the sum of the rest.

Now the subsets, using the choose, explore, un-choose shape.

/// Every way to choose some of the items (including none, and all).
pub fn subsets(items: &[i32]) -> Vec<Vec<i32>> {
    let mut all = Vec::new();
    let mut current = Vec::new();
    explore(items, 0, &mut current, &mut all);
    all
}

/// At each item, there are two roads: skip it, or take it.
fn explore(items: &[i32], index: usize, current: &mut Vec<i32>, all: &mut Vec<Vec<i32>>) {
    if index == items.len() {
        // Every item has been decided. Save a copy, because `current` changes.
        all.push(current.clone());
        return;
    }

    explore(items, index + 1, current, all); // road 1: skip it

    current.push(items[index]); // road 2: take it
    explore(items, index + 1, current, all);
    current.pop(); // step back, so the caller finds `current` as it left it
}

Go through it in order.

• subsets sets up three things: the all list of answers, the current subset being built, and a call to explore.
• explore is the recursion. index says which item is being decided. When index reaches the end, every item has been decided, so that is a finished subset. It pushes a copy with clone(), because current will keep changing as the search goes on.
• Otherwise it takes the first road, skipping the item, and recurses.
• Then the second road. It pushes the item (choose), recurses (explore), and pops it off again (un-choose). That pop is the step back from the picture.

Both current and all are passed as &mut, a borrow the function may change. That way every call shares the same two lists, instead of copying them at each step.

Remember: whatever you add before the recursive call, you remove after it.

Now permutations, the ways to put items in a row. Three items give 3 × 2 × 1 = 6 orders. The shape is the same, with a loop for the roads.

/// Every way to put the items in a row, each item used once.
pub fn permutations(items: &[i32]) -> Vec<Vec<i32>> {
    let mut all = Vec::new();
    let mut current = Vec::new();
    let mut used = vec![false; items.len()];
    arrange(items, &mut used, &mut current, &mut all);
    all
}

fn arrange(items: &[i32], used: &mut [bool], current: &mut Vec<i32>, all: &mut Vec<Vec<i32>>) {
    if current.len() == items.len() {
        all.push(current.clone());
        return;
    }
    for i in 0..items.len() {
        if used[i] {
            continue; // already placed earlier in this row
        }
        used[i] = true;
        current.push(items[i]);
        arrange(items, used, current, all);
        // Undo both changes before trying the next item in this spot.
        current.pop();
        used[i] = false;
    }
}

At each place in the row, the loop tries every item that has not been used yet. used[i] remembers which are already placed. After trying an item, both changes are undone together: pop takes it off the row, and used[i] = false makes it available again.

The standard library has no function for subsets or permutations. (The itertools crate does, if you ever want one in a project.) What it gives you are the small pieces used above.

• split_first and split_at cut a slice without copying it, which is what makes the recursion on a slice cheap.
• clone() copies the list being built, so a saved answer does not change later.
• Vec::push and Vec::pop are the choose and un-choose, and they are both O(1).
• Closures and nested fn items keep a helper close to the function that uses it. The solutions to the practice problems tuck their helper inside.

If a recursion is slow because it solves the same smaller problem again and again, that is the sign for lesson 19, where you remember the answers instead.

The honest news: the number of answers explodes. Twenty items have more than a million subsets. Backtracking is fine for small inputs, and very slow for large ones. Pruning helps, which means giving up on a road early when you can already tell it cannot work. You will do that in the practice problems.

Each starter has a todo!(), a placeholder that panics if it runs. Replace it with your code.

pub fn fast_pow(base: u64, exp: u32) -> u64 {
    todo!("what if you halve the exponent?")
}

/// `base` to the power `exp`, in about log(exp) calls instead of exp calls.
pub fn fast_pow(base: u64, exp: u32) -> u64 {
    if exp == 0 {
        return 1;
    }
    let half = fast_pow(base, exp / 2);
    if exp % 2 == 0 {
        half * half
    } else {
        half * half * base // an odd exponent has one left over
    }
}

pub fn count_subset_sums(nums: &[u32], target: u32) -> usize {
    todo!("take it or skip it, and stop early when you go over")
}

/// How many subsets of `nums` add up to exactly `target`.
pub fn count_subset_sums(nums: &[u32], target: u32) -> usize {
    // `left` is how much is still needed from the items from `index` on.
    fn count(nums: &[u32], index: usize, left: u32) -> usize {
        if index == nums.len() {
            return usize::from(left == 0); // 1 if we hit the target exactly
        }
        let skip = count(nums, index + 1, left);
        // Prune: an item bigger than what is left can never be taken.
        let take = if nums[index] <= left {
            count(nums, index + 1, left - nums[index])
        } else {
            0
        };
        skip + take
    }
    count(nums, 0, target)
}

pub fn n_queens(n: usize) -> usize {
    todo!("one queen per row; which columns are still safe?")
}

/// How many ways to put `n` queens on an `n` by `n` board so that none
/// can capture another.
pub fn n_queens(n: usize) -> usize {
    // Which columns and which two kinds of diagonal already hold a queen.
    let mut cols = vec![false; n];
    let mut slash = vec![false; 2 * n];
    let mut backslash = vec![false; 2 * n];

    fn place(
        row: usize,
        n: usize,
        cols: &mut [bool],
        slash: &mut [bool],
        backslash: &mut [bool],
    ) -> usize {
        if row == n {
            return 1; // every row has a queen
        }
        let mut ways = 0;
        for col in 0..n {
            // Squares on one diagonal share `row + col`, and on the other
            // they share `row - col`, shifted up so it is never negative.
            let (a, b) = (row + col, row + n - 1 - col);
            if cols[col] || slash[a] || backslash[b] {
                continue; // this square is attacked
            }
            cols[col] = true;
            slash[a] = true;
            backslash[b] = true;
            ways += place(row + 1, n, cols, slash, backslash);
            cols[col] = false; // backtrack
            slash[a] = false;
            backslash[b] = false;
        }
        ways
    }
    place(0, n, &mut cols, &mut slash, &mut backslash)
}

Recursion questions test whether you can trust a function to solve a smaller copy of itself. Backtracking questions add the habit of undoing.

• Spot the signals. "All ways", "every combination", "all arrangements", "generate", "place without conflict", and "does any path exist" point to backtracking. A tree or a nested structure points to plain recursion.
• Name the base case first. Say what the simplest input is and what its answer is. Then say how each call gets closer to it.
• Draw the tree. Sketch two levels of choices for a tiny input, like the picture in this lesson. It shows the interviewer your plan, and it exposes the cost.
• Use the three beats. Say "choose, explore, un-choose" out loud, and make sure every choice has a matching undo.
• Say what you copy. A saved answer must be a copy, as in current.clone(). Pushing the list you are still changing is the classic bug.
• Prune early. Name any condition that lets you give up on a road: a sum gone over, a square attacked, a letter already used. Pruning turns a hopeless search into a workable one.
• State the cost honestly. Subsets are O(2ⁿ) and permutations are O(n!). Say that this is fine for small n, and that a repeating sub-problem is the cue to remember answers, as in dynamic programming.
• Mention stack depth. Recursion depth equals stack space. If the depth could be huge, offer an explicit stack with a Vec instead.

Made by VeraStack Labs