abyiber.com
Back to Blog

Recursion: Solving Problems by Solving Smaller Problems

How recursive functions work, why they need base cases, and how to think about call stacks, recurrence relations, and memoization.

2021-01-17
Share
CS Fundamentalsrecursionalgorithms

Terminology

Recursion
A technique where a function calls itself to solve a smaller instance of the same problem. The solution to the original problem is built from the solutions to the smaller instances.
Base Case
The simplest instance of the problem that can be solved directly without further recursion. Every recursive function must have at least one base case to avoid infinite recursion.
Recursive Case
The part of a recursive function that breaks the problem into smaller subproblems and calls itself on those subproblems.
Call Stack
The region of memory that stores stack frames for each active function call. Each recursive call adds a new frame; returning pops it. Excessive recursion can exhaust this memory (stack overflow).
Stack Overflow
An error that occurs when the call stack exceeds its allocated memory, typically caused by missing or unreachable base cases.
Recurrence Relation
A mathematical equation that defines a function in terms of its value at smaller inputs. Used to analyze the time complexity of recursive algorithms, e.g. $T(n) = 2T(n/2) + O(n)$.
Memoization
An optimization technique that caches the results of expensive recursive calls so that repeated calls with the same arguments return instantly. Converts exponential-time recursion into polynomial time for overlapping subproblems.
Tail Recursion
A special form of recursion where the recursive call is the very last operation in the function. Some compilers optimize tail recursion into a loop, eliminating stack frame overhead.

What & Why

Recursion is a problem-solving technique where a function solves a problem by calling itself on a smaller version of the same problem. It keeps breaking things down until it hits a base case that can be answered directly, then builds the answer back up.

Why does this matter? Many problems have a naturally recursive structure. Trees are recursive (a tree is a node with subtrees). Sorting can be recursive (sort two halves, then merge). Parsing nested expressions, traversing file systems, generating permutations, and solving puzzles like the Tower of Hanoi all have elegant recursive solutions.

Recursion is also the foundation for dynamic programming, divide-and-conquer algorithms, and backtracking. Understanding how recursive calls map to the call stack, how to write correct base cases, and how to analyze recurrence relations is essential for the rest of this curriculum.

Key properties:

  • Self-similarity: the problem at size n has the same structure as the problem at size n-1 (or n/2, etc.)
  • Base case required: without a termination condition, recursion runs forever (stack overflow)
  • Call stack cost: each recursive call uses stack memory; deep recursion can be expensive
  • Elegance vs. efficiency: recursive solutions are often cleaner to write but may need memoization or conversion to iteration for performance

How It Works

The Recursive Pattern

Every recursive function follows the same template:

  1. Check the base case: if the input is small enough, return the answer directly
  2. Otherwise, break the problem into one or more smaller subproblems
  3. Recursively solve each subproblem
  4. Combine the results to form the answer to the original problem

Example: Factorial

The factorial function $n! = n \times (n-1) \times \ldots \times 1$ has a natural recursive definition:

  • Base case: $0! = 1$
  • Recursive case: $n! = n \times (n-1)!$

Visualizing the Call Stack

When computing $\text{factorial}(4)$, the call stack grows as each call waits for its subproblem to resolve, then unwinds as results return:

Winding (calls) Unwinding (returns) factorial(4) factorial(3) factorial(2) factorial(1) factorial(0) = 1 base case reached returns 1 1 * 1 = 1 2 * 1 = 2 3 * 2 = 6 4 * 6 = 24

Divide and Conquer

Many efficient algorithms use recursion to split a problem in half:

  • Merge sort: split the array in half, recursively sort each half, merge the sorted halves
  • Binary search: check the middle element, recurse on the left or right half
  • Quick sort: pick a pivot, partition around it, recurse on each partition

These algorithms have recurrence relations of the form $T(n) = aT(n/b) + f(n)$, solvable by the Master Theorem.

Memoization

Some recursive problems have overlapping subproblems, meaning the same subproblem is solved multiple times. The classic example is the Fibonacci sequence:

$F(n) = F(n-1) + F(n-2)$, with $F(0) = 0$, $F(1) = 1$

Without memoization, computing $F(n)$ makes $O(2^n)$ calls because each call branches into two. With memoization (caching results), each value is computed once, reducing the time to $O(n)$.

Tail Recursion

A recursive call is in tail position if it is the very last thing the function does before returning. Some languages and compilers optimize tail calls by reusing the current stack frame, effectively converting the recursion into a loop with $O(1)$ stack usage.

Not all recursive functions can be made tail-recursive. Functions that need to combine results after the recursive call (like factorial: $n \times \text{factorial}(n-1)$) require an accumulator parameter to achieve tail form.

Complexity Analysis

Pattern Recurrence Time Example
Linear recursion $T(n) = T(n-1) + O(1)$ $O(n)$ Factorial, list traversal
Binary recursion (no overlap) $T(n) = 2T(n/2) + O(n)$ $O(n \log n)$ Merge sort
Binary recursion (overlap) $T(n) = T(n-1) + T(n-2)$ $O(2^n)$ Naive Fibonacci
With memoization $T(n) = O(1)$ per unique call $O(n)$ Memoized Fibonacci
Logarithmic recursion $T(n) = T(n/2) + O(1)$ $O(\log n)$ Binary search

Space Complexity

Recursive functions use $O(d)$ stack space where $d$ is the maximum recursion depth. For linear recursion, $d = n$. For divide-and-conquer, $d = \log n$. Memoization adds $O(n)$ space for the cache.

$\text{Stack space} = O(\text{max recursion depth})$

The Master Theorem (Simplified)

For recurrences of the form $T(n) = aT(n/b) + O(n^c)$:

  • If $\log_b a < c$: $T(n) = O(n^c)$ (work at root dominates)
  • If $\log_b a = c$: $T(n) = O(n^c \log n)$ (work is equal at each level)
  • If $\log_b a > c$: $T(n) = O(n^{\log_b a})$ (work at leaves dominates)

Implementation

Factorial (Pseudocode)

FUNCTION factorial(n):
    IF n = 0 THEN RETURN 1          // base case
    RETURN n * factorial(n - 1)      // recursive case

Factorial with Tail Recursion (Pseudocode)

FUNCTION factorial(n):
    RETURN factorialHelper(n, 1)

FUNCTION factorialHelper(n, accumulator):
    IF n = 0 THEN RETURN accumulator
    RETURN factorialHelper(n - 1, n * accumulator)

Fibonacci with Memoization (Pseudocode)

cache ← empty map

FUNCTION fib(n):
    IF n <= 1 THEN RETURN n
    IF n IN cache THEN RETURN cache[n]
    result ← fib(n - 1) + fib(n - 2)
    cache[n] ← result
    RETURN result

Merge Sort (Pseudocode)

FUNCTION mergeSort(arr):
    IF length(arr) <= 1 THEN RETURN arr
    mid ← length(arr) / 2
    left ← mergeSort(arr[0..mid-1])
    right ← mergeSort(arr[mid..end])
    RETURN merge(left, right)

FUNCTION merge(left, right):
    result ← empty list
    i ← 0, j ← 0
    WHILE i < length(left) AND j < length(right):
        IF left[i] <= right[j] THEN
            APPEND left[i] TO result
            i ← i + 1
        ELSE
            APPEND right[j] TO result
            j ← j + 1
    APPEND remaining elements of left and right TO result
    RETURN result

Tower of Hanoi (Pseudocode)

FUNCTION hanoi(n, source, target, auxiliary):
    IF n = 1 THEN
        MOVE disk 1 FROM source TO target
        RETURN
    hanoi(n - 1, source, auxiliary, target)
    MOVE disk n FROM source TO target
    hanoi(n - 1, auxiliary, target, source)

Real-World Applications

  • File system traversal: listing all files in a directory tree is naturally recursive: process the current directory, then recurse into each subdirectory
  • JSON/XML parsing: nested data structures are parsed recursively, with each nested object or array triggering a recursive descent
  • Compilers: recursive descent parsers match grammar rules by calling functions that correspond to grammar productions
  • Fractals and graphics: fractal generation (Sierpinski triangle, Koch snowflake, Mandelbrot zoom) uses recursion to apply the same pattern at decreasing scales
  • Backtracking algorithms: solving Sudoku, N-Queens, and maze problems by trying a choice, recursing, and undoing the choice if it leads to a dead end
  • Git merge: three-way merge algorithms recursively find common ancestors and resolve conflicts in nested directory structures

Key Takeaways

  • Recursion solves a problem by reducing it to smaller instances of itself, bottoming out at a base case
  • Every recursive call adds a frame to the call stack; the maximum depth determines stack space usage
  • Overlapping subproblems cause exponential blowup; memoization fixes this by caching results
  • Divide-and-conquer algorithms (merge sort, binary search) use recursion to split problems in half, achieving $O(n \log n)$ or $O(\log n)$ time
  • The Master Theorem gives a quick way to determine the time complexity of divide-and-conquer recurrences