Recursion

Topic type: Algorithm Paradigm LeetCode problems: 100+

---

Core Concepts

Recursive function — a function that calls itself with a strictly smaller or simpler input, eventually reaching a state that can be answered directly.

Base case — the condition under which the function returns immediately without a recursive call. Every correct recursive function has at least one base case; a missing or unreachable base case causes infinite recursion and a stack overflow.

Recursive case — the rule that reduces the current problem to one or more smaller subproblems and combines their results into the answer for the current call.

Call stack frame — each invocation of a recursive function occupies a stack frame holding its local variables, parameters, and return address. Stack depth equals the maximum nesting depth of active calls at any moment.

Recurrence relation — a mathematical expression of the recursive case: T(n) in terms of T(smaller inputs). Solving the recurrence gives the time complexity (master theorem, substitution, or recursion tree).

Inductive correctness — the standard way to reason about recursion: assume the recursive calls return the correct answer for all smaller inputs (inductive hypothesis), then verify the current function combines them correctly. This matches mathematical induction exactly.

Subproblem structure — the shape of how a problem decomposes:

• Linear — one recursive call on input of size n−1 or n/k
• Tree (branching) — two or more recursive calls per level; total calls is exponential without memoization
• Divide and conquer — subproblems are disjoint and results are merged
• Backtracking — recursive calls explore a search tree; a call is abandoned (backtracked) when a branch is proven invalid

Mutual recursion — two or more functions that call each other; each individual function has no self-call, but the call chain cycles. Requires careful shared base-case handling.

Tail call — a recursive call that is the very last operation in the function (its result is returned directly without further computation). Tail calls can in principle be optimised to iteration by the compiler/runtime; Python does not perform this optimization.

---

Internal Representation

Choosing between implicit call stack and explicit stack is a space-complexity swap, not a time-complexity one — both consume O(depth) memory; explicit stack just moves that memory from the call stack to the heap, avoiding OS-level stack limits.

---

Types / Variants

See dynamic-programming.md for full coverage of memoised recursion and DP. See backtracking.md for full coverage of backtracking patterns.

---

Key Algorithms

Factorial / Power (Linear Recursion Template)

Reduce n to n−1 (or halve for fast exponentiation). O(n) time / O(log n) for fast power; O(depth) stack space.

Key insight: the base case terminates the chain; the recursive case defines the step. Every linear recursion follows this skeleton.

Binary Search (Recursive)

Search left or right half depending on midpoint comparison. O(log n) time, O(log n) stack.

Key insight: each call discards exactly half the search space; depth is bounded by log₂n. The iterative version uses O(1) space, making it preferred in practice.

Merge Sort

Split array at midpoint, recursively sort each half, merge the two sorted halves. O(n log n) time, O(n) auxiliary space for the merge buffer, O(log n) stack.

Key insight: disjoint halves mean subproblems never interfere; merge is the only non-trivial step. The recurrence T(n) = 2T(n/2) + O(n) solves to O(n log n) by the master theorem.

Quick Sort

Partition around a pivot (all smaller elements left, larger right), then recurse on each part. O(n log n) average, O(n²) worst-case (sorted input with bad pivot), O(log n) average stack.

Key insight: after partitioning, the pivot is permanently in its correct position; no merge step needed. Randomised pivot selection prevents worst-case inputs.

Tower of Hanoi

Move n−1 disks from source to auxiliary using target as spare, move disk n directly to target, move n−1 disks from auxiliary to target. 2ⁿ − 1 moves total, O(n) stack.

Key insight: the only legal move for the largest disk is direct; everything else serves to clear the path. This is the canonical example of decrease-and-conquer.

Generating All Subsets / Power Set

At each index, branch: include the current element or skip it. O(2ⁿ) time and space, O(n) stack.

def subsets(i, current):
    if i == len(nums): result.append(current[:])
    else:
        subsets(i+1, current)           # skip
        current.append(nums[i])
        subsets(i+1, current)           # include
        current.pop()

Generating All Permutations

Swap each remaining element into the current position, recurse, swap back. O(n! · n) time, O(n) stack.

Key insight: the swap-before and swap-after (restore) pattern ensures each call sees a complete, temporarily rearranged array rather than a copy.

Reverse a Linked List (Recursive)

Recurse to the tail, then relink on the way back: head.next.next = head; head.next = None. O(n) time, O(n) stack.

Key insight: post-order processing — the return from depth carries the new head upward while the linking happens on unwind.

Tree Height / Depth (Post-order)

height(node) = 1 + max(height(left), height(right)) with height(None) = 0. O(n) time, O(h) stack.

See trees.md for full tree recursion coverage.

GCD (Euclidean Algorithm)

gcd(a, b) = gcd(b, a % b) with gcd(a, 0) = a. O(log min(a,b)) time, O(log min(a,b)) stack.

Key insight: a % b < b strictly, so the second argument decreases strictly toward 0.

Flood Fill

Mark the current cell, recurse in 4 directions only on valid unmarked matching cells. O(R×C) time, O(R×C) stack in the worst case (path graph shaped grid).

See depth-first-search.md for the full DFS treatment of grid and graph recursion.

---

Advanced Techniques

Memoisation (Top-Down DP)

Solves: Any recursion with overlapping subproblems — Fibonacci, LCS, knapsack, coin change, longest paths in DAGs. Mechanism: Cache the return value keyed by the function's arguments using @functools.cache or a manual dict. On a repeated call, return the cached result immediately instead of recomputing. When to prefer over bottom-up DP: When only a subset of states is ever reached (sparse state space), when the recursion structure is naturally clear, or when the topological order for bottom-up is difficult to determine. Complexity: O(states × work per state) vs. exponential without caching.

Tail Recursion → Iteration Conversion

Solves: Eliminates stack overflow on deeply recursive functions where the recursive call is the last operation. Mechanism: Introduce an explicit accumulator parameter; the function passes the partial result forward instead of building it on the return. Then mechanically replace the tail call with a loop: re-assign parameters and continue. Python requires this conversion manually. When to prefer: Whenever recursion depth can exceed ~500 and the recursion is tail-recursive in structure (linear recursion processing a sequence). Not applicable to tree recursion where both branches' results are combined. Complexity: Same time; O(1) stack instead of O(n).

Divide and Conquer with Merge

Solves: Problems where the answer for a range [l, r] requires combining answers from [l, mid] and [mid+1, r] — inversion count, count of smaller numbers after self, merge sort tree queries. Mechanism: Recursively solve each half, then process the inter-half relationship during the merge step. The merge step is where the cross-subproblem information (e.g., inversions spanning both halves) is collected. When to prefer over sorting or BIT alone: When the cross-half relationship has a structure that the merge step can exploit in O(n) per level (e.g., sorted order of one half lets you binary-search against the other). Complexity: O(n log n) for most split-merge algorithms.

---

Problem Taxonomy

By Problem Category

Problem Signal → Technique

---

Common Patterns

---

Edge Cases & Pitfalls

• Missing or unreachable base case — the function recurses infinitely. Consequence: stack overflow. Fix: trace through the smallest inputs (n=0, n=1, empty list, null node) and verify the base case matches each.

• Base case too broad — returning early for inputs that still need recursive processing (e.g., returning 0 for an empty node when the caller expects 1). Carefully match the base case to the problem's definition of the smallest valid input.

• Not making progress toward the base case — the recursive call does not strictly reduce the input size (e.g., passing n instead of n-1, or passing the same node). Consequence: infinite recursion on valid inputs. Fix: confirm that each recursive call's argument is strictly closer to a base case.

• Forgetting to restore state after backtracking — when a shared mutable object (list, set, grid cell) is modified before a recursive call and not restored afterward, sibling recursive calls see corrupted state. Always pair every mutation with an undo.

• Python recursion limit — default is 1000 frames. Inputs with depth > ~500 raise RecursionError. Fix: sys.setrecursionlimit(n + 100) at script start, or convert to iterative using an explicit stack.

• Exponential blowup from tree recursion — a naïve Fibonacci-style recursion recomputes exponentially many identical calls. Symptom: TLE on n > 30–40. Fix: add memoization (@cache) or switch to bottom-up DP.

• Confusing pre-order and post-order logic — computing the answer at the current node before children are processed (pre-order) when the children's results are needed first (post-order). This silently produces wrong answers. Always ask: "do I need my children's results to compute mine?" — if yes, recurse first.

• Off-by-one in list/string recursion — passing nums[1:] creates a new list each call, giving O(n²) total work and O(n) space per call. Prefer passing an index i as a parameter and indexing into the original array.

• Mutable default argument — def f(current=[]) in Python: the default list persists across calls. Always use current=None and initialise inside the function.

• Treating None and 0 as equivalent — in tree recursion, failing to distinguish node is None from node.val == 0 causes bugs in path-sum and leaf-detection logic.

• Deep copy vs. shallow copy of path — recording result.append(current) instead of result.append(current[:]) stores a reference; all recorded entries will reflect the final state of current. Always copy before appending to results.

---

Implementation Notes

• sys.setrecursionlimit must be called at module level before any recursive function is invoked; calling it inside the function body has no effect for the current call chain.
• @functools.cache (Python 3.9+) is equivalent to @functools.lru_cache(maxsize=None); use it for memoisation unless memory is a concern.
• @cache requires all arguments to be hashable; convert lists to tuples and sets to frozensets before passing as arguments.
• Slicing a list in each call (nums[1:]) is O(n) per call and O(n) extra space; always prefer threading an index.
• To simulate recursion iteratively, use a list as a stack and push tuples of (arguments, phase) where phase tracks whether child calls have completed — this mirrors the frame state.
• For mutual recursion, ensure both functions are defined before either is called; in Python, forward declaration is not needed as long as calls happen at runtime, not at definition time.
• Stack depth for balanced binary tree recursion is O(log n); for skewed trees (path-like) it is O(n) — test against degenerate inputs.
• When the recursion has two symmetric base cases (e.g., l > r and l == r), handle both explicitly to avoid subtle wrong-answer bugs on single-element ranges.

---

Cross-Topic Relations

---

Interview Reference

Must-Know Problems

Mathematical / Linear Recursion

• Pow(x, n) (LC 50) — fast exponentiation, halving recursion
• Reverse Linked List (LC 206) — return-from-depth carry-up
• Swap Nodes in Pairs (LC 24) — linked list structural recursion
• K-th Symbol in Grammar (LC 779) — decrease-and-conquer on row structure

Tree Structural Recursion

• Maximum Depth of Binary Tree (LC 104) — post-order, height
• Invert Binary Tree (LC 226) — pre-order, structural mirror
• Symmetric Tree (LC 101) — mutual recursive comparison
• Path Sum (LC 112) — top-down propagation
• Path Sum II (LC 113) — backtracking path accumulation
• Flatten Binary Tree to Linked List (LC 114) — post-order relinking
• Lowest Common Ancestor of a Binary Tree (LC 236) — post-order search
• Construct Binary Tree from Preorder and Inorder (LC 105) — divide and conquer on arrays

Divide and Conquer

• Sort an Array / Merge Sort (LC 912) — prototypical D&C
• Count of Smaller Numbers After Self (LC 315) — merge sort with cross-count
• The Skyline Problem (LC 218) — divide and merge intervals

Combinatorial Generation (Backtracking)

• Subsets (LC 78), Subsets II (LC 90) — include/exclude branching
• Permutations (LC 46), Permutations II (LC 47) — swap-and-recurse
• Combination Sum (LC 39), Combination Sum II (LC 40) — pruned backtracking
• Letter Combinations of a Phone Number (LC 17) — multi-branch per position
• Generate Parentheses (LC 22) — constrained branching

Structural Transformation

• Reverse Linked List II (LC 92) — recursive partial reversal
• Flatten Nested List Iterator (LC 341) — recursive flattening
• Decode String (LC 394) — recursive parsing with brackets

Advanced

• Regular Expression Matching (LC 10) — recursive matching with * lookahead
• Scramble String (LC 87) — divide and conquer with memoization
• Expression Add Operators (LC 282) — backtracking with running evaluation

Additional LeetCode Coverage

• Power of Three (LC 326)
• Permutation Sequence (LC 60)

Clarification Questions to Ask

• What are the constraints on input size? (Determines whether recursion depth is safe or an explicit stack / iterative approach is needed.)
• Can the input be null or empty? (Base case definition depends on this.)
• Is the structure guaranteed to be acyclic? (Cycles in graphs require a visited set; trees do not.)
• For enumeration problems: are duplicates in the input allowed? If so, should duplicate results be eliminated?
• For path problems: does "path" mean root-to-leaf, or any node-to-node? (Changes base case and traversal direction.)
• Is the order of generated results significant?

Common Interview Mistakes

• Writing the recursive case before confirming the base case is correct — always define and test the base case first.
• Making a copy of the entire input on each call (arr[1:] in a loop) instead of threading an index — produces O(n²) time and memory inadvertently.
• Forgetting to restore mutable state after a backtracking call — always trace a path that fails and verify the undo executes.
• Applying tree-recursion (two calls) to a problem that requires only linear recursion — unnecessary branching causes exponential blowup.
• Not memoizing a branching recursion with overlapping subproblems — produces TLE even on medium-sized inputs.
• Returning a value from within the recursive case without combining both branches — silently discards one subtree's answer in tree problems.
• Using result.append(path) instead of result.append(path[:]) — all appended entries reference the same list and reflect its final state.

Typical Follow-Up Escalations

• "Now do it iteratively (no recursion)" → convert to explicit stack; for post-order, use the (node, processed) tuple pattern.
• "The input list has 10^6 elements in a chain" → iterative conversion or sys.setrecursionlimit; explain the tradeoff.
• "This is too slow" → identify whether subproblems overlap; add @cache for top-down memoization, or restructure as bottom-up DP.
• "Now return all solutions, not just one" → convert early-return search to a collecting backtracking search with path accumulation.
• "Can you do this in O(1) extra space?" → check if tail-recursive structure allows accumulator conversion; O(h) stack is irreducible for inherently recursive structures like trees.
• "What's the time complexity?" → derive the recurrence, apply master theorem (divide and conquer) or sum the call tree nodes (backtracking).