What are recursion and backtracking and how do they appear in coding interviews?
Recursion is a technique where a function calls itself to solve smaller subproblems until reaching a base case. Backtracking is a recursive strategy that incrementally builds candidates for a solution and abandons candidates that cannot possibly lead to a valid answer. Together they power a large category of coding interview problems involving combinations, permutations, constraint satisfaction, and search.
Recursion and backtracking problems are some of the most frequently asked in software engineering interviews at top companies. They appear in coding challenges because they test whether candidates can think about problems in terms of smaller subproblems, recognize when a brute-force search can be pruned, and implement clean recursive solutions without bugs. Understanding the patterns deeply — not just memorizing solutions — is what separates candidates who pass these questions from those who freeze.
The Mental Model for Recursion
Every recursive solution has the same structure. Before writing a single line of code, identify these three components:
Base case: The condition under which recursion stops. A missing or incorrect base case causes infinite recursion. Ask: "What is the smallest version of this problem I can solve directly?"
Recursive case: The logic that reduces the problem to a smaller version of itself. Ask: "How can I express the solution to this problem in terms of solutions to smaller versions of this problem?"
Return value: What the function returns at each level and how the return values combine. Ask: "What does this function return, and how do I combine sub-results into the full result?"
A useful mental exercise before coding: write a plain English recursive definition. For example, "the factorial of N equals N times the factorial of N minus 1, with factorial of 0 equal to 1." If you can say it naturally, you can code it.
The Call Stack and Recursion Depth
Interviewers care about recursion depth because deep recursion causes stack overflow. Understand the constraints:
| Problem Size | Typical Max Depth | Stack Concern |
|---|---|---|
| N = 10 | 10 levels | None |
| N = 1,000 | 1,000 levels | Low risk |
| N = 100,000 | 100,000 levels | High risk — consider iteration |
| Tree depth = O(log N) | ~17 levels for N=100,000 | None |
| Unbalanced tree | O(N) levels | Risk if N is large |
When the problem size suggests deep recursion, mention tail call optimization or an iterative equivalent as an alternative. Python does not optimize tail calls. Java and C++ have limited optimization. This awareness impresses interviewers.
Core Recursion Pattern: Divide and Conquer
Divide and conquer splits a problem into independent subproblems, solves them recursively, and merges the results.
function solve(input):
if base_case(input):
return base_result
left = solve(left_half(input))
right = solve(right_half(input))
return merge(left, right)
Classic examples: merge sort, binary search, maximum subarray (Kadane's reduces to this), finding the Nth power of X.
Interview tip: When you see a problem on an array or list and the brute force is O(N^2), ask yourself whether divide and conquer can bring it to O(N log N). It often can.
Core Backtracking Pattern
Backtracking has a distinct structure from pure recursion. It makes a choice, recurses, then undoes the choice. The "undo" step is what makes it backtracking rather than pure recursion.
function backtrack(state, choices):
if goal_reached(state):
add state to results
return
for choice in choices:
if valid(choice, state):
make_choice(choice, state)
backtrack(state, remaining_choices)
undo_choice(choice, state) # <-- this is the backtracking step
The three questions to answer before coding any backtracking problem:
- What is the state? What information do I track at each recursive call?
- What are the choices? What decisions do I make at each step?
- What is the goal? When do I record a complete solution?
"Every backtracking problem I have ever seen in an interview fits into the same template. Once I recognized that, I stopped memorizing solutions and started recognizing problem shapes." — Senior Software Engineer, Google
Permutations
Generate all orderings of a list. This is the canonical backtracking problem.
State: Current permutation being built, set of used indices
Choices: Any unused index from the original array
Goal: Permutation has same length as input array
Time complexity: O(N * N!) — N! permutations each requiring O(N) to record
Space complexity: O(N) for the recursion stack
Pruning: If elements are duplicates, sort first and skip duplicate elements at the same recursion level to avoid generating identical permutations.
Combinations
Generate all subsets of size K from N elements. Less explosive than permutations because order does not matter.
State: Current combination being built, starting index
Choices: Any index from start to end of array (enforcing start prevents duplicate combinations)
Goal: Combination has length K
Time complexity: O(K * C(N,K)) where C(N,K) is the binomial coefficient
Space: O(K) stack depth
Pruning opportunity: If remaining elements are fewer than needed elements, stop early. This is a simple but effective pruning step that interviewers notice.
Subsets (Power Set)
Generate all possible subsets — every combination of 0 to N elements.
State: Current subset, current index
Choices: Include or exclude current element
Goal: Processed all elements
This is the simplest backtracking problem because there is no validity check — every state at "index equals length" is a valid result.
Time complexity: O(N * 2^N) — 2^N subsets each up to O(N) to record
Combination Sum
Given a list of candidates and a target, find all combinations that sum to the target. Candidates can be reused (variant: each used once).
State: Current combination, current sum, starting index
Choices: Each candidate from starting index forward
Goal: Current sum equals target
Pruning: If current sum exceeds target, stop. This pruning is only possible if candidates are sorted (which they may not be — sort them first).
Reuse variant: Allow same index to recurse again (don't increment start index). No-reuse variant: increment start index after including element.
This problem has two common variants that interviewers mix. Confirm before coding: "Can I use the same element multiple times?"
Letter Combinations of a Phone Number
Map digits to letters (classic phone keypad) and generate all possible letter combinations.
State: Current string being built, current digit index
Choices: Each letter corresponding to current digit
Goal: String length equals number of digits
This is a pure backtracking problem with no pruning — all branches lead to valid results. Its simplicity makes it a good warm-up or early screening question.
N-Queens
Place N queens on an N×N chessboard such that no two queens attack each other.
State: Row-by-row placement, sets tracking occupied columns and diagonals
Choices: Each column in the current row
Goal: All N rows have a queen placed
Efficiency trick: Use three sets to track occupied columns, positive diagonals (row - col is constant on a positive diagonal), and negative diagonals (row + col is constant on a negative diagonal). This makes validity checking O(1).
This problem appears at senior levels and tests whether candidates can represent constraints efficiently.
"N-Queens is a beautiful problem because the naive check is O(N^2) but the efficient check is O(1) with the right data structure. I use it to separate candidates who understand the problem from candidates who understand the concept." — Engineering Manager, Meta
Sudoku Solver
Fill a 9×9 Sudoku grid so every row, column, and 3×3 box contains digits 1-9 without repetition.
State: Current board state
Choices: Each digit 1-9 for the current empty cell
Goal: No empty cells remain
Pruning: Only attempt digit if not already in current row, column, or box. Track occupied sets for O(1) lookup.
Order of filling: Finding the most constrained empty cell first (minimum remaining values heuristic) dramatically reduces backtracking but is not required for interview correctness.
Word Search
Given a 2D board of characters, determine if a word can be formed by sequentially adjacent cells.
State: Current position, current index in word, visited cells set
Choices: Four adjacent cells (up, down, left, right)
Goal: All characters of word matched
Key detail: Mark a cell as visited before recursing and unmark it after (backtracking). Forgetting to unmark is the most common bug in this problem.
Time complexity: O(M * N * 4^L) where M and N are board dimensions and L is word length. This is the worst case — pruning cuts it significantly in practice.
Word Break II
Given a string and a word dictionary, return all ways to segment the string into valid words.
This combines backtracking with memoization. Without memoization it has exponential time complexity. With memoization on the starting index, overlapping subproblems are solved once.
State: Current starting index in string
Choices: Every prefix of the remaining string that exists in dictionary
Goal: Reached end of string
This is a harder problem that tests whether candidates recognize when backtracking alone is insufficient and memoization is needed.
Palindrome Partitioning
Given a string, return all ways to partition it into palindromes.
State: Current partition, current starting index
Choices: Every prefix of remaining string
Validity: Only proceed if current prefix is a palindrome
Goal: Reached end of string
Optimization: Precompute a 2D boolean table is_palindrome[i][j] using dynamic programming, then use it for O(1) palindrome checks during backtracking.
| Problem Type | Key Pattern | Common Pruning |
|---|---|---|
| Permutations | Use visited set | Skip duplicate elements at same level |
| Combinations | Start index advances | Stop when remaining < needed |
| Subsets | Include/exclude at each step | None — all branches valid |
| Combination Sum | Running sum tracking | Stop when sum > target |
| Path finding | Mark/unmark visited | Stop when out of bounds |
| Constraint satisfaction | Track constraints with sets | Skip invalid choices early |
Recognizing When to Use Backtracking
Backtracking is appropriate when the problem asks you to:
- Find all solutions (not just one)
- Find one solution in a combinatorial search space
- Generate all permutations, combinations, or subsets
- Solve a constraint satisfaction problem (Sudoku, N-Queens)
Backtracking is usually the wrong choice when:
- You only need to count solutions (use dynamic programming instead)
- The problem has a greedy property (optimal choice is always clear)
- The search space is not exponential
When an interviewer asks a "find all" or "generate all" question, backtracking should be your first instinct.
Time Complexity of Backtracking Solutions
Backtracking problems have exponential worst-case complexity. This is often acceptable if the problem inherently requires it, but you should state the complexity clearly.
| Problem | Time Complexity | Why |
|---|---|---|
| Permutations | O(N * N!) | N! arrangements, O(N) to copy each |
| Combinations (k of n) | O(k * C(n,k)) | C(n,k) combinations, O(k) to copy |
| Subsets | O(N * 2^N) | 2^N subsets, O(N) to copy |
| N-Queens | O(N!) | N choices for row 1, N-1 for row 2, etc. |
| Sudoku | O(9^(empty cells)) | 9 choices per empty cell |
Pruning reduces actual runtime dramatically but does not change the worst-case Big O. Distinguish these in your answer: "The worst case is O(N!) but pruning makes this much faster in practice for typical inputs."
Recursion vs. Iteration for Interviews
Some recursive solutions can be converted to iterative ones using an explicit stack. When should you offer this?
- When the interviewer asks about stack overflow risk
- When the recursion depth can be very large
- When the language does not optimize tail calls
Offer the iterative version as a follow-up: "The recursive solution has O(N) space from the call stack. I could rewrite it iteratively using an explicit stack to keep the same time complexity but make the space usage more explicit." This demonstrates awareness interviewers reward.
"I always ask candidates to analyze the recursion depth of their solution. Most people write recursive code without thinking about whether it will stack overflow on large inputs. The ones who think about it proactively are the ones I want to hire." — Staff Engineer, Amazon
Debugging Recursive Solutions
Common bugs in recursive solutions and how to catch them:
Missing base case: Symptom is infinite recursion. Fix: trace through the smallest possible input.
Wrong base case condition: Symptom is returning early or too late. Fix: verify what state corresponds to "done."
Forgetting to undo state in backtracking: Symptom is incorrect results where previous choices contaminate later branches. Fix: add print statements to see state at each level, verify state is clean on entry.
Wrong return value combination: Symptom is correct structure but wrong values. Fix: trace through a small example by hand before coding.
A useful debugging practice: write a small 3-4 element example, trace through it manually, and verify your code produces the expected result before running it.
Frequently Asked Questions
How do I know if I should use recursion or dynamic programming? Use recursion (with backtracking) when you need all solutions or when the problem involves constraint satisfaction. Use dynamic programming when you need one optimal solution and the problem has overlapping subproblems and optimal substructure. Many problems can use both — backtracking to explore, memoization to avoid repeating work.
What is the most common mistake in backtracking problems? Forgetting to undo state changes after recursion. If you add an element to a list, mark a cell visited, or modify any shared state before recursing, you must reverse that change after the recursive call returns. Missing this step causes one branch's choices to contaminate other branches.
How do I handle problems where elements can be repeated? Sort the input first. Then at each recursion level, if the current element equals the previous element (same level, not parent level), skip it. This requires distinguishing between "same level duplicate" (skip) and "reusing same element deeper in the tree" (allowed depending on problem variant). Track which situation applies by using index-based navigation rather than element-based navigation.
References
- Skiena, S. S. (2008). The Algorithm Design Manual (2nd ed.). Springer.
- Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley.
- Leetcode. (2023). Backtracking Problem Set. Leetcode.com.
- Aziz, A., Lee, T.-H., & Prakash, A. (2018). Elements of Programming Interviews. CreateSpace.
- Gayle Laakmann McDowell. (2015). Cracking the Coding Interview (6th ed.). CareerCup.