Skip to content

Recursion & Backtracking

Lesson 1 of 7 in Recursion, Trees & Graphs · 50 min · Intermediate

Solve a smaller copy of the problem; undo choices that fail.

Introduction

A set of Russian dolls is closed. You can only open one doll at a time, and you can't peek inside. How do you count how many dolls are in the set?

Open the big doll and you find a smaller doll that is a copy of the same puzzle: "how many dolls are inside this one?" So you ask that question again, on the smaller doll, and again, until you hold the tiniest doll, the one that doesn't open.

That tiniest doll is the only one that knows its answer without asking anybody. What does it say, and what does everyone above it do with that answer?

Lesson overview

This lesson will show you how to:

  • Explain how a base case stops a recursive call from running forever.
  • Trace the call stack for factorial as calls go down and return.
  • Implement a recursive function that solves a smaller copy of the problem.
  • Trace backtracking through subsets, choosing then unchoosing each element.
  • Prune a branch as soon as it cannot lead to a valid answer.
  • Spot why naive recursive Fibonacci repeats work and runs slowly.

The picture

fact(3)fact(2)fact(1)fact(3)fact(2)fact(1)waits for fact(2)base case: no more callscall stack, newest on topCall tree with 3 calls: 0 returned, 1 active, 2 pending, 0 pruned. Active: fact(1). Call stack, bottom to top: fact(3); fact(2); fact(1).

Mental model

Picture a stack of sticky notes on your desk, one for every task you have started but not finished. When a task needs a smaller task done first, you stick a new note on top and work on that one. When the top note is finished, you tear it off and the note under it can carry on.

Backtracking is exploring a maze this way. At every fork you pick a corridor and walk in, and at a dead end you step back to the fork, undo that choice, and try the next corridor.

Don't follow every call in your head: solve one step, trust the smaller call to return the right answer, and make sure some call stops.

Words to know

base case
The smallest version of the problem, answered directly with no further calls. Without it the calls never stop.
recursive case
The step where the function calls itself on a smaller input and uses what comes back.
call stack
The pile of calls that have started but not finished. A new call goes on top, and returning removes it.
stack overflow
What happens when the stack gets too deep, usually from a missing base case or a huge input. The program crashes (Python stops at around a thousand calls by default).
backtracking
Building an answer one choice at a time, and stepping back to undo a choice as soon as that branch is finished or cannot work.
choose / explore / unchoose
The backtracking rhythm: add a choice to the path, recurse to see where it leads, then remove it so the next choice starts from a clean path.
pruning
Cutting off a branch as soon as you can tell it can't lead to a valid answer, so you never explore it.

Watch it run

Step with → or Next. When a question pops up, make your guess. Try your own input once the guided run ends.

Getting the demo ready…

Recognise it

Most of the skill is noticing the clue in the problem statement.

Reach for it when

  • Yes: The problem asks for all subsets, permutations, combinations or arrangements, so the answer is a list of lists of choices.
  • Yes: Every step has a few options, and you must be able to undo one to try the next.
  • Yes: The problem contains a smaller copy of itself: a tree, a nested structure, or "solve the left half and the right half".
  • Yes: The input is tiny (n of about 10 to 20), which says an exponential search is expected.

Not this when

  • No: You only need a count or a best value, and the same sub-problems keep coming back: dynamic programming remembers them instead of re-solving.
  • No: A simple rule is provably safe at each step, like always taking the meeting that ends first: greedy never needs to explore the other branches.
  • No: The depth could be 100,000 or more: plain recursion may overflow the stack, so loop or keep your own stack.

Which pattern fits?

  1. Which pattern? 1 of 5

    Given an array of distinct integers, return all of its possible permutations.

  2. Which pattern? 2 of 5

    You climb stairs taking 1 or 2 steps at a time. Count the distinct ways to reach step 45, and return only the count.

  3. Which pattern? 3 of 5

    Given n pairs of parentheses, generate every well-formed combination of them.

  4. Which pattern? 4 of 5

    In a maze grid, find the fewest moves from the start to the exit.

  5. Which pattern? 5 of 5

    Given meeting time intervals, find the most meetings one person can attend without overlap.

The code

First the idea in plain steps. Then the same idea as real code, line for line.

Pseudocode
  1. 1res = [], path = [], then explore(0)
  2. explore(i):
  3. 2if i == n: save a copy of path, return (base case)
  4. 3if path is shorter than the limit: (else prune)
  5. 4choose: add nums[i] to path
  6. 5explore(i + 1)
  7. 6unchoose: remove it from path
  8. 7explore(i + 1) again, without nums[i] (skip)
  9. 8return res

The faint numbers are the rules in the Rule Rail under the stage. Same numbers, same order.

Getting the replay ready…

def subsets(nums, limit):
    res = []
    path = []

    def explore(i):
        if i == len(nums):
            res.append(path[:])
            return
        if len(path) < limit:
            path.append(nums[i])
            explore(i + 1)
            path.pop()
        explore(i + 1)

    explore(0)
    return res
Time · O(n · 2ⁿ)Space · O(n) extra
  • Every number is taken or skipped, so there are 2ⁿ leaves, and saving each subset copies up to n numbers: O(n · 2ⁿ) time.
  • Extra space is the call stack plus the path, both at most n deep: O(n). The list of answers is output, and it is not counted.
  • Save a copy of the path (path[:] in Python, new ArrayList<>(path) in Java). If you save the path itself, every saved answer is the same list, and unchoose empties it.
  • Unchoose must exactly undo choose. If it doesn't, the next branch starts from a dirty path and every answer after it is wrong.
  • Prune as early as you can: a branch cut near the root saves a whole subtree. With the limit, a full path never takes another number.
  • Plain recursion that re-solves the same sub-problem, like fib(n) = fib(n - 1) + fib(n - 2), repeats work: fib(3) is computed twice inside fib(5). Remembering answers fixes it, and that is the dynamic-programming lesson.

Worked examples

Real interview problems, solved with the same recipe.

Open on LeetCode (opens in a new tab)

The Fibonacci numbers start with F(0) = 0 and F(1) = 1, and each next number is the sum of the two before it. Given n, return F(n).

Input

n = 4

Output

3

Approach

  1. The base cases are n = 0 and n = 1: F(n) is n itself, no calls needed.
  2. The recursive case is F(n) = F(n - 1) + F(n - 2), two calls on smaller inputs.
  3. Written plainly, this solves the same F(k) again and again and takes exponential time.
  4. Store each answer in a memo the first time you compute it, and the work drops to one call per k.
def fib(n):
    memo = {}

    def go(k):
        if k < 2:
            return k
        if k not in memo:
            memo[k] = go(k - 1) + go(k - 2)
        return memo[k]

    return go(n)
Time · O(n)Space · O(n)

Knowledge check

Test yourself first. Try to answer these in your own words, then take the quiz below to check.

  1. What happens to a recursive function that has no base case?
  2. In backtracking, what does the unchoose step do?
  3. Why do we save a copy of the path, like path[:], instead of the path itself?
  4. What is the time of generating all subsets of n numbers, and why?
  5. Why is fib(n) = fib(n - 1) + fib(n - 2) slow for a big n when written as plain recursion?

Question 1 of 5

What happens to a recursive function that has no base case?

Assignment

Pick one, try it cold for ten minutes, then come back for the hint.

0 of 8 solved

  1. Solve Reverse Linked List (opens in a new tab) (LeetCode, easy)

    Hint: Trust that the call on head.next hands back a reversed rest of the list, then fix the one link between head and it.

  2. Solve Pow(x, n) (opens in a new tab) (LeetCode, medium)

    Hint: A power is the square of a power half as big, so you can halve the problem instead of shrinking it by one. Watch negative n.

  3. Solve Merge Two Sorted Lists (opens in a new tab) (LeetCode, easy)

    Hint: The smaller head must come first. Its next is the merge of what remains: a smaller copy of the same problem.

  4. Solve Combination Sum (opens in a new tab) (LeetCode, medium)

    Hint: A number may be reused, so recurse from the same index, and prune once the running sum passes the target.

  5. Solve Combinations (opens in a new tab) (LeetCode, medium)

    Hint: Like subsets, but you stop when the path has k numbers. Think about when a branch can no longer reach k.

  6. Solve Letter Combinations of a Phone Number (opens in a new tab) (LeetCode, medium)

    Hint: Each digit is one level of the tree and its letters are the choices at that level.

  7. Solve Generate Parentheses (opens in a new tab) (LeetCode, medium)

    Hint: Count how many ( and ) you have used. A ) is only allowed while there are more ( than ), and that rule is your pruning.

  8. Solve N-Queens (opens in a new tab) (LeetCode, hard)

    Hint: Place one queen per row. Try each column, skip the ones that are attacked, and unchoose when a row has no safe spot.

Additional resources