Recursion & Backtracking
Curriculum
A structured path to mastering recursive problem decomposition and state-space exploration through decision trees.
What This Pattern Is Really About
Breaking problems into smaller identical subproblems. Each recursive call operates on a reduced input with the same structure.
Explicit branching structure of choices. Each node represents a decision point; edges represent choices; leaves are solutions or dead ends.
Systematic exploration with state restoration. Make choice, recurse, undo choice. Guarantees all paths explored without state leakage.
Termination conditions that halt recursion. Define when problem is trivially solvable without further decomposition.
Mental Model & Invariant
Recursion is structured problem reduction with explicit state contracts.
"At each recursive call, the problem structure remains identical but the input size decreases. State is either preserved (immutable) or explicitly restored (backtracking)."
Break this, and you get infinite recursion or incorrect results.
Call Stack Contract
Define parameters, return type, and what each call guarantees. Every level must honor this contract.
State Invariant
What remains true across all recursive levels. Immutable state is passed down; mutable state must be restored after exploration.
Base Case First
Always define termination conditions before recursive cases. Base cases are non-negotiable—they prevent infinite recursion.
When to Think "Recursion & Backtracking"
sensorsStrong Signals
Generate all combinations/permutations
Explore all paths in tree/graph
Divide-and-conquer structure
Choice at each step with constraints
Subproblems have identical structure
Solution requires exhaustive search
ruleConstraint Signals
Must explore entire solution space
Decisions are reversible
Problem decomposes recursively
No greedy solution exists
Variants You Must Master
Pure Recursion
No state modification. Return values only. Immutable parameters.
Each call returns result; no side effects.
Backtracking with State
Modify state, explore, restore. Explicit undo after recursion.
State restored after each branch explored.
Memoization (Top-Down DP)
Cache subproblem results. Avoid recomputation.
Each subproblem computed once.
Divide and Conquer
Split problem, recurse on parts, combine results.
Subproblems independent; combine step merges.
How to Learn This Pattern
Draw the Decision Tree
Sketch the tree explicitly on paper. Each node is a state; edges are choices. Identify leaves (base cases) and internal nodes (recursive cases).
Define Recursive Signature
Write function signature: parameters (what changes), return type (what you compute). This is your call stack contract.
Identify Base Cases
When is the problem trivially solvable? When do you stop recursing? Write these conditions first—before any recursive logic.
Define Recursive Case
How do you decompose the problem? What choices exist? How do you combine results from recursive calls?
Verify State Management
Is state immutable (pass copies) or mutable (restore after recursion)? Trace what happens to state across calls.
Trace Execution
Walk through a small input by hand. Draw the call stack. Verify base cases hit, state is correct, and results combine properly.
Canonical Problem List
auto_awesome_motionFoundation
Subsets
Generate all subsets of a set. Binary choice at each element.
Permutations
Generate all orderings. Backtrack with used array or swapping.
Combinations
Choose K elements from N. Prune when remaining insufficient.
N-Queens (4x4)
Place N queens on board. Backtrack with column/diagonal tracking.
auto_awesome_motionIntermediate
Word Search
Find word in grid. Backtrack with visited marking.
Palindrome Partitioning
Partition string into palindromes. Backtrack on valid cuts.
Combination Sum
Find combinations summing to target. Prune when sum exceeds.
Letter Combinations of Phone Number
Generate all letter combinations. Tree of choices per digit.
Generate Parentheses
Generate valid parentheses. Track open/close counts.
auto_awesome_motionAdvanced
Sudoku Solver
Fill 9x9 grid with constraints. Backtrack on invalid placements.
Expression Add Operators
Insert operators to reach target. Track current value and last operand.
Word Break II
Segment string into dictionary words. Backtrack with memoization.
Restore IP Addresses
Partition string into valid IP. Validate segments during recursion.
Common Mistakes
Missing or Incorrect Base Cases
Infinite recursion or stack overflow. Function never terminates.
Write base cases first. Verify every recursive path eventually hits a base case.
Not Restoring State After Backtracking
State leaks across branches. Subsequent explorations see modified state from previous branches.
Explicitly undo every state modification after recursive call returns. Use add/recurse/remove pattern.
Passing Mutable State Without Copying
All recursive calls share same state object. Modifications affect other branches.
Pass copies of mutable state or use immutable data structures. Verify each call has independent state.
No Progress Toward Base Case
Infinite recursion. Input size doesn't decrease or termination condition never met.
Verify each recursive call moves closer to base case. Check that parameters change meaningfully.
Confusing Recursion with Iteration
Trying to think iteratively about recursive problems. Misses the decomposition structure.
Focus on: what does this call do? What do recursive calls return? How do I combine results?
Interview Guidance
What they test
- →Base Case Identification
- →State Management Precision
- →Decision Tree Articulation
Strategy
Avoid "I'll use recursion" without structure. Instead: "I'll explore all choices at each step. Each recursive call handles a smaller subproblem. Base case is when no more choices remain."
The Verbal Template
"When [condition], the problem is trivially solved. I return [value]."
"At this step, I can choose [option A] or [option B]. Each choice leads to a recursive call."
"I make a choice, recurse on the smaller problem, then [combine/backtrack]."
"I [pass immutable copy / modify and restore] state to ensure branches don't interfere."
When You've Mastered It
Draw decision tree immediately
Base cases defined before recursion
State management explicit and correct
Call stack contract articulated clearly
Backtracking restore logic automatic
Trace execution without debugger
What This Unlocks Next
Dynamic Programming
Recursion with memoization. Cache subproblem results to avoid recomputation.
Graph Traversal
DFS is recursive backtracking on graphs. BFS uses explicit queue instead of call stack.
Divide and Conquer
Recursive decomposition with independent subproblems and combine step.
State-Space Search
Systematic exploration of solution spaces with pruning and optimization.