Recursion and Backtracking Cheat Sheet for Coding Interviews
- Every recursive function has three jobs: base case, recursive case, and return value — missing any one causes silent failures like returning
None. - Recursion space equals stack depth, not total calls: O(n) for linear chains, O(log n) for halving, O(h) for tree DFS.
- The backtracking template is choose-explore-unchoose: always copy state with
path[:]on collection or every result points to the same mutable list. - Three tree shapes determine complexity before you write a line: subsets O(n·2^n), permutations O(n·n!), combinations O(k·C(n,k)).
- Pruning slashes exponential runtimes: constraint, bound, and symmetry pruning each eliminate a different class of dead branches.
- Never memoize backtracking:
lru_cachecaches return values but skips the side-effect mutations that build your result list.
Your interview is in 30 minutes. You don't need another tutorial. This recursion and backtracking cheat sheet covers the templates, complexity rules, pruning patterns, and bug traps that actually come up, with the exact facts you'll reach for under pressure.
Every Recursive Function Has Three Jobs
Base case, recursive case, and the return value. All three must be right, or nothing works.
def sum_to(n): if n == 0: # 1. base case: when you stop return 0 return sum_to(n - 1) + n # 2. recursive case: smaller subproblem # 3. return value: propagated back up
Before writing the first line, answer three questions: what is the smallest valid input (your base case), how does each call reduce the problem toward it, and what does one call return to its parent.
The most common bug: writing solve(n - 1) instead of return solve(n - 1). The recursive call runs, but the return value silently disappears. Your function returns None. The interviewer watches you stare at it for three minutes.
Recursion Space Is Depth, Not Total Calls
The call stack holds one frame per active call. Once a frame returns, it's gone. So space = O(maximum depth), not O(total calls).
| Pattern | Stack depth | Space |
|---|---|---|
| Linear chain (factorial, linked list) | n | O(n) |
| Halving each call (binary search) | log n | O(log n) |
| Tree DFS (height h) | h | O(h) |
| Backtracking (max depth d) | d | O(d) |
Python's default limit is 1,000 frames. Hitting it raises RecursionError before the OS kills you. You can raise it with sys.setrecursionlimit(n), but in an interview, just acknowledge the risk for large n and offer to convert to iteration if the depth is unbounded. See recursion space complexity for the full breakdown.
The Master Theorem (and When You Don't Need It)
For divide-and-conquer, use the Master Theorem. For linear recursion, just count the levels.
The Master Theorem applies to T(n) = aT(n/b) + O(n^d):
| Compare a vs b^d | Time complexity |
|---|---|
| a < b^d | O(n^d) (top-level work dominates) |
| a = b^d | O(n^d · log n) (work spreads evenly across all levels) |
| a > b^d | O(n^(log_b a)) (leaf work dominates) |
Common results worth having cold:
| Algorithm | Recurrence | Time |
|---|---|---|
| Binary search | T(n) = T(n/2) + O(1) | O(log n) |
| Merge sort | T(n) = 2T(n/2) + O(n) | O(n log n) |
| Factorial | T(n) = T(n-1) + O(1) | O(n) |
| Fibonacci (naive) | T(n) = T(n-1) + T(n-2) | O(2^n) |
| Fibonacci (memoized) | n states × O(1) each | O(n) |
For T(n) = T(n-1) + O(1): n levels, O(1) each, total O(n). No theorem needed.
The Backtracking Template Is Three Operations
Choose, explore, unchoose. Every backtracking solution is a variation on this.
def backtrack(state, choices): if is_complete(state): result.append(state[:]) # copy, never reference return for choice in choices: if is_valid(choice, state): state.append(choice) # choose backtrack(state, next_choices) # explore state.pop() # unchoose
The state[:] copy on collection is not optional. If you append state directly, every entry in your result list points to the same mutable list. By the time the function finishes, they all show the empty final state. You run your solution, get back a list of empty lists, and have a small personal crisis. This is the single most common backtracking bug. More on backtracking bugs.
The backtracking template is exactly this. If you forget the copy, you'll need one of these.
Every Backtracking Problem Has One of Three Tree Shapes
The shape determines the complexity before you write a line of code.
Subsets (include or skip each element)
Binary decision at each of n levels. Every possible subset is a leaf.
- Time: O(n · 2^n): 2^n leaves, O(n) to copy each
- Space: O(n): call stack depth equals n
def subsets(nums): result = [] def backtrack(start, path): result.append(path[:]) for i in range(start, len(nums)): path.append(nums[i]) backtrack(i + 1, path) path.pop() backtrack(0, []) return result
Permutations (use each element once, order matters)
n choices at level 1, n-1 at level 2, and so on.
- Time: O(n · n!): n! leaves, O(n) to copy each
- Space: O(n)
def permute(nums): result = [] def backtrack(path, used): if len(path) == len(nums): result.append(path[:]) return for i, n in enumerate(nums): if not used[i]: used[i] = True path.append(n) backtrack(path, used) path.pop() used[i] = False backtrack([], [False] * len(nums)) return result
Combinations (choose k from n, order doesn't matter)
Choose k elements from n, moving only forward through the array.
- Time: O(k · C(n, k)): C(n,k) leaves, O(k) to copy each
- Space: O(k)
Which shape is it? If order matters, permutations. If you pick exactly k items, combinations. If each element is in or out, subsets.
Pruning Kills Dead Branches Early
Adding one validity check before recursing can reduce runtime from minutes to milliseconds on hard inputs.
Three categories:
-
Constraint pruning. The partial state already violates a hard rule. Skip the whole subtree. In N-Queens, check column and diagonal conflicts before placing.
-
Bound pruning. Even the best possible completion from here can't beat the current best solution. Used in optimization variants like word search or TSP approximations.
-
Symmetry pruning. Two sibling choices produce the same result. Take only one. In Subsets II with duplicates, skip any
nums[i] == nums[i-1]wherei > start.
# Symmetry pruning for duplicates (sort nums first) for i in range(start, len(nums)): if i > start and nums[i] == nums[i - 1]: continue path.append(nums[i]) backtrack(i + 1, path) path.pop()
The sort before the call is not optional. It makes equal elements adjacent, which is what the duplicate check depends on. See pruning in backtracking for the full taxonomy.
Tree DFS: Process Order Is Everything
Most tree problems are depth-first search with a choice of where to process each node.
def dfs(node): if not node: return # preorder: process here (parent before children) dfs(node.left) # inorder: process here (left, root, right) dfs(node.right) # postorder: process here (children before parent)
When to use each:
| Order | Use when |
|---|---|
| Preorder | Building a copy, serialization, prefix-style problems |
| Inorder | Extracting BST elements in sorted order |
| Postorder | Parent value depends on children (height, diameter, path sums from leaves) |
Memoization Turns Recursion Into DP
If the same inputs always produce the same output and the same inputs repeat, cache the result.
from functools import lru_cache @lru_cache(maxsize=None) def fib(n): if n <= 1: return n return fib(n - 1) + fib(n - 2)
Time after memoization = (number of distinct states) × (work per state, not counting recursive calls).
Fibonacci: n states × O(1) work = O(n). Grid paths: m×n states × O(1) work = O(m·n). Coin change with k denominations and amount A: A×k states × O(1) work = O(A·k).
Do not memoize backtracking functions. Backtracking works by mutating state and undoing it. The function has side effects. lru_cache caches return values, not side effects. The cache returns the right value while silently skipping the mutation that builds your result list. Your output is empty and you have no idea why. You've been warned.
Bugs That Pass Tests and Fail Interviews
Run this checklist before you say you're done.
- Missing base case. What happens at empty input, single element, or n=0? Each deserves a mental trace.
- Off-by-one base case. Returns early by one level, or one too late.
- Aliasing. Appending
pathinstead ofpath[:]into the result list. Your result is a list of identical empty lists. Congratulations. - Dropped return.
solve(n - 1)computes the answer and throws it away. The function returnsNone. This is the bug that looks correct for thirty seconds. - Modifying the input array. The calling frame still depends on the original.
- Stack overflow. Linear recursion on n = 10^5 crashes Python at depth 1,000. Note it and offer iteration.
The energy when you fix the dropped return and something else breaks. Progress.
Recursion and Backtracking Complexity Reference
| Problem type | Time | Space |
|---|---|---|
| Subsets | O(n · 2^n) | O(n) |
| Permutations | O(n · n!) | O(n) |
| Combinations C(n,k) | O(k · C(n,k)) | O(k) |
| Memoized recursion | O(states × work) | O(states + depth) |
| Tree DFS | O(n) | O(h) |
| Binary search (recursive) | O(log n) | O(log n) |
| Merge sort | O(n log n) | O(n) |
Reading a reference helps. Saying it out loud under interview conditions is what actually transfers. SpaceComplexity runs voice-based mock interviews on backtracking and recursion problems with rubric-based feedback on your communication, not just your code.