Recursion Practice Problems

How to Use This Problem List

Recursion problems fall into a small number of structural patterns. Recognising the pattern within two minutes of reading is the key skill — not the implementation itself.

The two most important questions for any recursion problem:

1. ›What is the smallest version of this problem? (→ base case)
2. ›How does solving a smaller version help solve the full problem? (→ recursive case)

If you can answer both clearly before writing code, the implementation follows mechanically.

Pattern 1: Linear Recursion — Reduce and Return

The simplest pattern. One recursive call per level, problem shrinks by a fixed amount (usually 1 or 1/2), result is computed by combining the current level's data with the sub-call's result.

Complexity target: O(n) time, O(n) space (call stack).

Recognition signal: "recursively compute X for n", "check property of n", "transform string/number one step at a time". A single chain of calls where each level does O(1) work.

Pattern 2: Divide and Conquer

Split the problem into two or more smaller subproblems of roughly equal size, solve each recursively, then merge the results. The recursion tree is a balanced binary tree.

Complexity target: O(n log n) for sorting, O(log n) for search, O(n log n) for most divide-and-conquer.

Recognition signal: "O(log n)", "divide in half", "sort and merge", "closest/farthest pair". The problem naturally halves at each level.

Pattern 3: Tree Recursion

Problems defined on tree data structures where the answer for a node depends on the answers for its children. Nearly every tree problem is recursive by nature.

Complexity target: O(n) time (visit every node once), O(h) space where h = tree height.

Recognition signal: "binary tree", "height/depth/balance", "path sum", "compare two trees", "ancestor". Any problem about a tree node's relationship to its subtrees.

Pattern 4: Backtracking — Generate All Solutions

Explore all possible arrangements, subsets, or paths by making a choice, recursing, and undoing the choice. The recursion tree has one branch per choice at each decision point.

Complexity target: O(2ⁿ) for subsets, O(n!) for permutations, problem-specific for others.

Recognition signal: "all possible", "generate all", "find all combinations/permutations/arrangements", "does any path exist". The word "all" or the need to explore every option is the trigger.

Pattern 5: Structural Recursion — Nested Data

The problem's data is recursively structured (nested lists, linked lists, expression trees). The base case is the atom of the structure.

Complexity target: O(n) where n is the total number of elements across all nesting levels.

Recognition signal: "nested", "linked list", "parse", "expand", "decode", "deep copy". The structure mirrors the recursion — the recursive call processes a structurally smaller version.

Pattern 6: Mathematical and Number Recursion

Problems where the recursion is defined by mathematical relationships — number theory, sequences, geometric progressions.

Complexity target: O(n) with memoisation for sequence problems, O(2ⁿ) without.

Recognition signal: "nth term of sequence", "number of ways to", "how many", "convert number". A mathematical recurrence relationship is explicit or implicit in the problem statement.

Recommended Study Order

Week 1 — Linear and Divide and Conquer
  Pattern 1 (Linear): Reverse String, Sum Digits, Check Palindrome
  Pattern 2 (D&C):    Binary Search, Merge Sort, Exponentiation

Week 2 — Tree Recursion
  Pattern 3 (Tree):   Max Depth, Same Tree, Path Sum, Invert Tree
  Pattern 3 (Hard):   Diameter, Balanced, Lowest Common Ancestor

Week 3 — Backtracking
  Pattern 4 (Easy):   Subsets, Combinations, Letter Combinations
  Pattern 4 (Medium): Permutations, Generate Parentheses, Combination Sum

Week 4 — Advanced Patterns
  Pattern 5 (Structural): Merge Two Lists, Flatten Nested, Decode String
  Pattern 6 (Math):       Fibonacci (memoised), Tower of Hanoi, Climbing Stairs
  Pattern 4 (Hard):       N-Queens, Sudoku Solver, Word Search

Problem-Solving Checklist for Recursion Problems

Before writing code, answer these questions:

1. IDENTIFY THE BASE CASE
   □ What is the smallest input where the answer is known directly?
   □ Is this base case reachable from every valid input?
   □ Are all boundary cases handled? (empty array, null, n=0, n=1)

2. IDENTIFY THE RECURSIVE CASE
   □ What smaller version of the problem does this call?
   □ Is the argument strictly closer to the base case?
   □ How is the sub-call's result combined with the current level?

3. DETERMINE THE PATTERN
   □ Single chain → linear recursion
   □ Split in half + merge → divide and conquer
   □ Tree node + children → tree recursion
   □ Build and undo choices → backtracking
   □ Nested structure → structural recursion

4. ESTIMATE COMPLEXITY
   □ How many recursive calls per node?
   □ How deep is the recursion tree?
   □ How much work per node (excluding sub-calls)?
   □ Total = nodes × work-per-node  OR  levels × work-per-level

5. CHECK FOR OPTIMISATION
   □ Are sub-problems repeated? → memoisation (top-down DP)
   □ Is the recursive call in tail position? → iterative loop
   □ Is recursion depth > ~1000 (Python) or ~10000 (Java)? → iterative with explicit stack

6. EDGE CASES
   □ Empty input (array, string, tree null)
   □ Single element
   □ All elements identical
   □ Maximum depth inputs (large n)

Pattern Recognition Quick Reference

Difficulty Progression Reference

Common Interview Topics by Company Focus

Product-based companies (FAANG-tier):

• ›Subsets, Permutations, Combinations — backtracking fundamentals
• ›Binary Tree problems (max depth, diameter, LCA) — tree recursion
• ›Merge Sort / QuickSelect — divide and conquer
• ›Word Search — 2D backtracking
• ›Generate Parentheses — constrained backtracking

Service-based and on-campus:

• ›Fibonacci (memoised), Tower of Hanoi — math recursion
• ›Reverse Linked List, Merge Two Sorted Lists — structural recursion
• ›Binary Search recursive — divide and conquer
• ›Factorial, Palindrome Check — linear recursion

Startup and mid-size tech:

• ›N-Queens, Sudoku Solver — constraint satisfaction backtracking
• ›Decode String, Flatten Nested List — structural recursion
• ›Climbing Stairs, Jump Game — math recurrence with memoisation
• ›Invert / Flatten Binary Tree — tree recursion

Progress Tracking

After solving each problem, record:

1. ›Pattern — which of the 6 patterns does this belong to?
2. ›Base case(s) — what were they and were any non-obvious?
3. ›Recursive case — how did it make progress toward the base?
4. ›Tree shape — linear, branching, balanced, unbalanced?
5. ›Complexity — what is O(time) and O(space)? How was it derived from the tree?
6. ›Optimisation — did repeated subproblems suggest memoisation or iteration?

The decisive signal that pattern recognition is working: when you see "generate all valid parentheses" and immediately think "backtracking — two choices per position (open or close), pruned by open_count ≤ n and close_count ≤ open_count" before reading the constraints.