Top 10 Recursion Problems for Coding Interviews That Actually Build Intuition

Most engineers learn recursion by solving 50 random LeetCode problems and hoping it clicks. It usually does not. You end up with 50 solved problems, zero intuition, and a Gmail inbox that looks like this:

Gmail inbox with label:rejections showing 50 of 50 emails, the cost of grinding without a plan

Solving 50 random problems, hoping recursion will click. Still waiting.

What actually builds intuition is solving fewer recursion problems, deliberately, in an order that reveals the full structure of recursive thinking.

This list is ten problems, ordered by what they teach. Work through them in sequence and you will cover every major recursion pattern that shows up in a coding interview: the call stack, divide-and-conquer, the backtracking family, tree synthesis, and the bridge to dynamic programming.

1. Fibonacci: Your CPU Will Hate You (At First)

LeetCode 509. Do not skip this because it feels too simple. Fibonacci is not a warmup. It is the complete arc from naive recursion to memoization to dynamic programming, compressed into one function.

The naive recursive solution is correct and catastrophically slow: O(2^n) time because fib(3) is recomputed dozens of times inside fib(10). Draw the recursion tree and you will see the problem with your own eyes. Run fib(50) without memoization and watch your terminal sit there judging you. Then add a dictionary cache and the exponential tree collapses to a linear chain.

def fib(n: int, memo: dict = {}) -> int:
    if n <= 1:
        return n
    if n not in memo:
        memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

That transformation, four lines turning an exponential function into a linear one, is the core idea behind memoization and every top-down DP solution you will write. Fibonacci makes you feel it rather than just read about it.

2. Maximum Depth of Binary Tree: Trust the Function You Just Wrote

LeetCode 104. This is the first tree problem everyone should solve, because it forces a mental model shift.

You cannot compute the depth of a tree by inspecting just the root. But you can trust that maxDepth(root.left) will return the correct depth of the left subtree. The skill being developed is the ability to define a function by what it returns, not by how the recursion implements it.

def maxDepth(root) -> int:
    if not root:
        return 0
    return 1 + max(maxDepth(root.left), maxDepth(root.right))

Three lines. The base case handles the null node. The recursive case assumes both subtrees report their depths correctly and computes the current node's depth from that. This "assume it works and build on it" pattern appears in almost every tree problem.

3. Merge Sort: The Recursion Tree Is the Complexity Proof

Merge sort earns a spot here for a reason that has nothing to do with sorting: the recursion tree makes the complexity visible.

You do not need to reason about O(n log n) abstractly. Draw the tree. Each level processes all n elements during the merge step. There are log n levels because you halve the array at each split. Total: O(n log n). The algorithm's efficiency is literally visible in how the recursion decomposes the problem.

This is why recursion time complexity and divide-and-conquer are best learned together, not separately. The split-recurse-combine skeleton reappears in segment trees, fast exponentiation, and the binary lifting algorithm.

4. Subsets: Every Problem Hides a Decision Tree

LeetCode 78. Subsets introduces the binary decision tree, and once you see it, you recognize it in every combination or subset problem for the rest of your career.

At each index in the array you make exactly one binary choice: include nums[i] in the current subset, or skip it. Two choices at each of n positions means 2^n leaf nodes, which is exactly how many subsets exist. The recursion tree is the count.

def subsets(nums: list[int]) -> list[list[int]]:
    result = []
    def backtrack(index: int, current: list[int]) -> None:
        result.append(current[:])
        for i in range(index, len(nums)):
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()
    backtrack(0, [])
    return result

Notice current.pop(). That is not cleanup. It is the undo step that makes the tree exploration correct. Every backtracking problem has an undo step. Forget it once and you will spend 45 minutes debugging output that looks almost right but never quite is. Subsets is where you should first internalize that instinct.

5. Permutations: Order Matters, and You Need to Track It

LeetCode 46. Subsets and permutations look similar at the surface. They are not. In subsets, order does not matter and you only move forward through the array. In permutations, every element can appear at every position.

The key difference is that permutations require you to track which elements are already placed, not just which index you started from. You are maintaining state across recursive calls and restoring it on the way back out.

This state-tracking instinct transfers directly to every harder backtracking problem: columns used in N-Queens, cells visited in Word Search, characters counted in constraint satisfaction. Permutations is where you should first practice maintaining and restoring that state correctly.

6. Generate Parentheses: Prune Before You Explore

LeetCode 22. This is where backtracking becomes interesting. The naive approach is to generate all 2^(2n) strings and filter for valid ones afterward. It is the algorithm equivalent of eating every item at a buffet to find out which ones you like. The recursive approach prunes during generation, and the difference is the lesson.

At each step you can add ( if your open-count is less than n, or ) if your close-count is less than your open-count. Those two constraints eliminate the entire invalid search space before you ever generate a bad string. Pruning determines whether a combinatorial solution runs in milliseconds or does not terminate. Generate Parentheses is the cleanest problem to see this.

The invariant here is simple. In harder problems it gets more complex. But the principle is the same: find the condition that makes a partial solution unrecoverable and cut there, not at the end.

7. Lowest Common Ancestor: Return Values Carry Information

LeetCode 236. This problem teaches a recursion pattern that the previous six do not: information flowing upward through the call stack.

In backtracking, state flows mostly downward and is undone on return. In LCA, each recursive call returns something meaningful, and the parent synthesizes the two results. If both the left and right subtrees return a non-null node, the current node is the LCA. If only one returns something, that result propagates up.

def lowestCommonAncestor(root, p, q):
    if not root or root == p or root == q:
        return root
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    return root if (left and right) else (left or right)

This postorder collect-and-synthesize pattern appears in path sum variants, binary tree cameras, maximum path sum, and dozens of other problems. Understanding it here unlocks the whole family.

8. Word Search: State Lives in the Grid

LeetCode 79. Most backtracking problems track visited state in a set passed as a parameter. Word Search forces a different approach: the state lives in the grid itself.

You mark a cell as visited by temporarily modifying its value. After the recursive call returns, you restore the original value. This mutation-and-restore pattern is faster than a separate visited matrix, but it is only correct if you restore state on every path, including the ones that fail.

Word Search is the best problem for building the instinct that the undo step is non-optional. It is easy to forget when state is implicit in a grid and you are chasing four directions at once. Get it right here and you get it right everywhere similar.

9. Decode Ways: Recursion to Memoization to Tabulation

LeetCode 91. Decode Ways closes the loop opened by Fibonacci.

At each position you can decode one digit (if nonzero) or two digits (if the resulting number is between 10 and 26). The recursion branches. The subproblems overlap: decoding from index 4 is called whether you arrive from index 2 or index 3. Add memoization and the exponential call tree collapses to O(n). Remove the recursion and replace it with a table and you have bottom-up DP.

This is the cleanest problem for experiencing the full pipeline: brute-force recursion, top-down with memoization, then tabulation. The dynamic programming framework powering every interview DP solution is visible here in its simplest form.

10. N-Queens: Three Constraints, One Set Each

LeetCode 51. N-Queens is the capstone. Place n queens on an n x n board with no two queens sharing a row, column, or diagonal.

The structure is the same as Generate Parentheses: place queens one row at a time, check constraints before placing, skip invalid columns early. The difference is three overlapping constraint sets, each tracked with a hash set, which reduces every constraint check from O(n) to O(1).

def solveNQueens(n: int) -> list[list[str]]:
    cols, diag1, diag2 = set(), set(), set()
    board = [['.' for _ in range(n)] for _ in range(n)]
    result = []

    def backtrack(row: int) -> None:
        if row == n:
            result.append([''.join(r) for r in board])
            return
        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue
            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)
            board[row][col] = 'Q'
            backtrack(row + 1)
            board[row][col] = '.'
            cols.remove(col)
            diag1.remove(row - col)
            diag2.remove(row + col)

    backtrack(0)
    return result

If you can write this cleanly, including the symmetric add-and-remove for all three constraint sets, you understand backtracking. The rest is variations.

The Recursion Problem Arc

These ten problems cover the full recursion curriculum. Fibonacci builds the memoization instinct. Max Depth teaches you to trust return values. Merge Sort shows you why divide-and-conquer has the complexity it does. Subsets through Generate Parentheses develop the backtracking family from simple to constrained. LCA introduces upward synthesis. Word Search makes state mutation explicit. Decode Ways bridges recursion to DP. N-Queens caps it all.

Work through them in order, coding each from scratch. After N-Queens, most recursion problems on LeetCode are recognizable variations or combinations of patterns you have already internalized. Maybe slightly annoying variations. But recognizable.

If you want to test your recursion under real interview conditions, where explaining your reasoning matters as much as writing correct code, SpaceComplexity runs voice-based mock interviews with rubric-based feedback across exactly the dimensions that interviewers score. Try it after you finish this list.