Skip to content

Recursion#

Recursion solves a problem by breaking it into smaller instances of the same problem until a base case stops the chain. Every recursive call adds a frame to the call stack.

Core components#

Part Role
Base case Simplest input; returns directly without further recursion
Recursive case Calls the function on a strictly smaller / simpler input
Progress Each step must move toward the base case (avoid infinite recursion) 
def factorial(n: int) -> int:
    if n <= 1:           # base case
        return 1
    return n * factorial(n - 1)   # recursive case; n decreases → progress

Time: O(n) — n recursive calls, O(1) work each.
Space: O(n) — call stack depth n.

Call stack intuition#

Call stack frames while evaluating factorial(4)

Each open call holds local variables until it returns. Deep recursion → stack overflow (Python default limit ~1000 frames, configurable).

When to use recursion#

Prefer recursion Prefer iteration
Trees and graphs (natural fit) Simple linear loops
Divide-and-conquer (merge sort, quick sort) Tail-recursive patterns easy to rewrite as loops
Backtracking (permutations, subsets) Performance-critical hot paths with deep depth
Problem definition is inherently recursive Stack depth may exceed limits

Recurrence and complexity#

Many recursive algorithms cost T(n) = a·T(n/b) + f(n). Intuition (formalized by the Master Theorem):

Pattern Example Typical time
Halve problem, O(1) combine Binary search O(log n)
Halve problem, O(n) combine Merge sort O(n log n)
Two half-sized subproblems + O(n) merge Merge sort O(n log n)
Single subproblem n−1 Factorial, linear search O(n)
Two subproblems size n−1 Naive Fibonacci O(2ⁿ) — needs memoization

Space often equals maximum recursion depth × frame size, unless tail-call optimized (Python does not optimize tail calls).

Memoization (top-down dynamic programming)#

Cache subproblem results to avoid recomputation.

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

Without memo: O(2ⁿ) time — exponential tree of calls.
With memo: O(n) time, O(n) space (cache + stack).

Head vs tail recursion#

Head recursion — recursive call happens, then more work on the way back (factorial).

Tail recursion — recursive call is the last operation; can be rewritten as a loop:

def factorial_iter(n: int) -> int:
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

In Python, prefer explicit loops when depth is large.

Recursion on trees#

Tree traversals are the canonical recursive use case:

def tree_height(node) -> int:
    if node is None:
        return -1                    # base: empty tree
    return 1 + max(
        tree_height(node.left),
        tree_height(node.right),
    )

Time: O(n) — visit every node once.
Space: O(h) — h = height; worst O(n) for a skewed tree, O(log n) for balanced.

Backtracking template#

Try a choice, recurse, undo if it fails:

def backtrack(path, choices):
    if is_complete(path):
        record(path)
        return
    for choice in choices:
        if not is_valid(choice, path):
            continue
        path.append(choice)      # choose
        backtrack(path, next_choices)
        path.pop()               # unchoose

Time: often exponential in input size (all subsets/permutations).
Space: O(depth) stack plus O(depth) current path.

Common pitfalls#

  1. Missing base case — infinite recursion.
  2. Not progressing toward base case — same argument size recursed forever.
  3. Ignoring stack depth — skewed tree or deep backtracking may hit limits.
  4. Redundant subproblems without memo — exponential blow-up (Fibonacci, repeated grid paths).

Debugging checklist#

  • What is the smallest input I can answer directly?
  • Does each recursive call use a strictly smaller state?
  • Can the same state be reached on multiple paths? → add memoization.
  • What is stack depth in the worst case?