A recursive function calls itself on a smaller input until it reaches a base case it can answer directly. Backtracking is recursion that builds candidates step by step and abandons (undoes) a partial candidate as soon as it cannot lead to a solution.
Base case + recursive case
Every recursion needs two parts: a base case that stops the recursion, and a recursive case that reduces the problem and calls itself. Miss the base case and the stack overflows.
Factorial, and subsets via backtracking
function fact(n):
if n <= 1: return 1 // base case
return n * fact(n - 1) // recursive case
function subsets(i, chosen):
if i == n: record(chosen); return
subsets(i+1, chosen + [A[i]]) // include A[i]
subsets(i+1, chosen) // exclude A[i]O(2^n) for subsets→O(n) stack depth
Each element is either in or out -> 2^n combinations.
⚡ The edge
- Write the base case first — it is both the stopping rule and the first thing that goes wrong if forgotten.
- Backtracking is 'choose, explore, un-choose': make a move, recurse, then undo the move so the next branch starts clean.
Worked example
Trace fact(4).
- fact(4) = 4 x fact(3); fact(3) = 3 x fact(2); fact(2) = 2 x fact(1).
- fact(1) hits the base case and returns 1.
- Unwinding: 2x1=2, 3x2=6, 4x6=24.
Answer: fact(4) = 24
Worked example
How many subsets does a 3-element set have, and why?
- For each element you make a binary choice: include it or exclude it.
- Three independent choices give 2 x 2 x 2 = 2^3 combinations.
- So there are 8 subsets (including the empty set).
Answer: 2^3 = 8 subsets
⚠ Watch out
- A missing or wrong base case causes infinite recursion and a stack overflow.
- Recursion uses O(depth) stack memory — deep recursion can run out of stack.
- In backtracking, undo the choice after recursing, or state leaks into sibling branches.