Recursion & backtracking

The idea

A recursive function hands a smaller copy of the problem to itself

The factorial of 4 is 4 × 3 × 2 × 1 = 24. Notice that 4! is just 4 × 3!, and 3! is 3 × 2!. Each factorial is defined by a smaller one, down to 1! = 1, which needs nothing smaller.

Recursion writes that down directly: a function that calls itself on a smaller input. Two parts make it work:

the base case, an input small enough to answer directly (1! = 1);
the recursive case, which shrinks the problem, calls itself and builds its answer from the result (n! = n × (n − 1)!).

The rule

Every recursive function needs a base case that returns without calling itself, and every other call must move closer to it. Miss either one and the calls never end.

The call stack

Every call waits on a stack until the calls it made return

When fact(4) calls fact(3), it can't finish yet: it needs the answer. So the program saves where fact(4) was and what its variables held, and starts fact(3). Those saved calls form the call stack: the newest call on top, the only one running.

The calls pile up until the base case, then unwind in reverse order, each one finishing the multiplication it was waiting to do. Last in, first out: exactly a stack, the structure from Stacks & queues.

Each waiting call takes memory, so recursion n levels deep uses O(n) space even when the function looks like it stores nothing. Too deep, and the program runs out of room for the stack: a stack overflow. Python stops at a depth of 1,000 by default; Java and JavaScript fail when the stack's memory runs out, which is often after some thousands of calls.

Writing one

Trust the smaller call and think only about one level

Tracing every call in your head doesn't scale. Instead, write a recursive function in four steps, and assume the smaller call already works:

Say what the function returns
"fact(n) returns n!". Be exact: this sentence is what you trust later.
Handle the base case
The smallest input, answered directly: if n ≤ 1, return 1.
Shrink the problem
Call the function on a smaller input: fact(n − 1), which by step 1 returns (n − 1)!.
Build the answer
Combine: return n × fact(n − 1).

Any recursion can also be written as a loop, sometimes with a stack of your own to stand in for the call stack. Prefer the loop when the depth could reach the thousands. Some languages can run a call that is the very last thing a function does without keeping its caller around, but Python and Java don't, so don't count on it.

Backtracking

Backtracking builds a solution one choice at a time, and undoes each choice

List every subset of [1, 2, 3]. For each item there are two choices, in or out, so there are 2 × 2 × 2 = 8 subsets. Recursion can make one choice per level: decide about item 0, then hand the rest of the list to a smaller call.

Backtracking is that recursion plus one habit. Keep one list, current, of the choices made so far. To explore "item i is in", append it, recurse, then remove it again before exploring "item i is out". When every item has been decided, current is a complete subset: save a copy.

The undo step is what makes it work. Without it, item 1 would still be in current while exploring the subsets that leave it out. The same three moves, choose, explore and undo, generate arrangements, combinations and paths through a maze, and they are the base of every backtracking solution.

Hard

Orders: the same moves, with a record of what's taken

Listing every order of a list uses the same choose, explore, undo, with one change: each level may pick any item not yet used, so a list of flags records what's taken. There are n! orders, and the recursion tree has one leaf per order.

The cost

The recursion tree shows how much work the calls do

Draw every call as a node and each call it makes as a child, and you get the recursion tree. Its shape is the cost:

factorial makes one call per level: a chain of n calls, O(n) time and O(n) stack;
subsets makes two calls per level: a tree with 2ⁿ leaves, one per subset, so O(2ⁿ) calls, and copying each subset out costs up to n more: O(n × 2ⁿ) time.

Items	Subsets (2ⁿ)	Calls in the tree (2ⁿ⁺¹ − 1)
3	8	15
10	1,024	2,047
20	1,048,576	2,097,151
30	about 1 billion	about 2 billion

Exponential work is unavoidable when the answer itself has 2ⁿ parts. When you only need some of them, such as subsets that add up to a target, backtracking can stop exploring a branch as soon as it can't work. Cutting branches early, called pruning, is where most of a backtracking solution's speed comes from.

Check yourself

4 questions

1. A recursive function has no base case. What happens when it runs?

2. fact(n) has no list or array in it. How much memory does fact(1000) need while it runs?

3. In the subsets code, what goes wrong if you delete the pop(current) line?

4. How many subsets does a list of 20 distinct items have?

Takeaways

Remember this

A recursive function calls itself on a smaller input; it needs a base case and must move toward it.
Waiting calls sit on the call stack, so recursion n deep uses O(n) memory, and too deep overflows it.
Write recursion by trusting the smaller call: define what it returns, handle the base case, shrink, combine.
Backtracking explores choices with choose, explore, undo, sharing one list of choices.
The recursion tree's size is the cost: one call per level is O(n), two per level is O(2ⁿ) calls.

Practice

Now solve some yourself

Mixed with topics you have practiced 0 unlocked

2 more once you have practiced Linked lists, Divide & conquer. Play one of its examples to the end and solve one of its problems to unlock them.

Problems open on their own sites (LeetCode, Codeforces, CodeChef, AtCoder, CSES) in a new tab. Tick Solved when you get it accepted there; your ticks decide which mixed problems open next.