Recursion and Divide and Conquer

Recursive thinking, the call stack, recurrence relations, divide-and-conquer design, and backtracking.

There is a particular moment in learning to program where recursion stops looking like a magic trick and starts looking like a tool — a moment when “a function that calls itself” stops sounding paradoxical and starts sounding like the most natural way to describe a huge class of problems. This chapter is aimed squarely at producing that moment, and then building on it: from the mechanics of recursive calls, to a systematic design strategy (divide and conquer) built on top of them, to the mathematical machinery (recurrence relations and the Master Theorem) that lets you predict how fast a recursive algorithm will run before you’ve finished writing it.

The Shape of a Recursive Solution

Every correct recursive function has exactly two ingredients:

A base case — an input simple enough to answer directly, without further recursion. This is what stops the recursion from going forever.
A recursive case — a way of expressing the answer to the current problem in terms of the answer to one or more smaller instances of the same problem.

Here is the smallest possible illustration, computing n!:

long long factorial(int n) {
    if (n <= 1) {
        return 1;                       /* base case */
    }
    return n * factorial(n - 1);        /* recursive case */
}

Read the recursive case as a sentence: “the factorial of n is n times the factorial of n - 1.” That sentence is both a mathematical truth and a complete algorithm — which is exactly the appeal of recursion. When a problem has a natural self-similar structure — when “solve the big version” can be phrased as “combine the answer to a smaller version with a little extra work” — recursion lets you write down that description almost verbatim and have it run.

Pause and think: Try writing factorial iteratively, with a loop and an accumulator variable. It’s not hard — but notice that the iterative version requires you to introduce a variable (the accumulator) that has no counterpart in the mathematical definition of factorial. The recursive version mirrors the definition; the iterative version mirrors the execution. Neither is “more correct,” but they optimize for different kinds of clarity. Learning to recognize, for a given problem, which framing makes the solution obvious rather than merely possible is a big part of what this chapter is trying to teach.

What Actually Happens: The Call Stack

To reason precisely about recursive code — its correctness, its cost in time, and (just as importantly) its cost in memory — you need an accurate mental model of what the computer does when one function calls another.

Every time a function is called, the program allocates a small block of memory called a stack frame, which holds that call’s parameters, local variables, and the address it should return to when it finishes. Stack frames are stacked on top of each other — last in, first out — in a region of memory called the call stack. When a function calls itself, a new stack frame is created for the inner call; the outer call’s frame stays put, patiently waiting, with its own copy of n and its own place to receive a return value.

Trace factorial(4) and you’ll see the stack grow to four frames deep before anything is computed, and then unwind:

factorial(4) calls factorial(3)
  factorial(3) calls factorial(2)
    factorial(2) calls factorial(1)
      factorial(1) returns 1                  <- base case reached, stack stops growing
    factorial(2) returns 2 * 1 = 2
  factorial(3) returns 3 * 2 = 6
factorial(4) returns 4 * 6 = 24

Two consequences fall directly out of this picture, and both connect straight back to the previous chapter:

Time: the total work is the number of calls times the work per call — here, n calls each doing O(1) work outside the recursive call, giving O(n) overall.
Space: the call stack holds up to n frames simultaneously at the deepest point, so this function uses O(n) space — not O(1), even though it allocates no arrays. Push n large enough (a few hundred thousand, depending on your platform and frame size) and factorial will crash with a stack overflow before it crashes with an integer overflow. Recursion is not free. Every recursive algorithm you design should be able to answer the question “how deep does this go, and can the stack survive that?”

Try it yourself: Predict, without running it, what happens if you call factorial(-1). Then check your prediction. What does this tell you about the relationship between “having a base case” and “having a correct base case that covers every input that can actually reach it”?

Worked Example: Tower of Hanoi

The Tower of Hanoi is a puzzle with three pegs (source A, auxiliary B, destination C) and n disks of different sizes stacked on peg A in decreasing order. The goal: move all disks to peg C, using peg B as scratch space, obeying one rule at all times — a larger disk may never rest on a smaller one.

This sounds like it requires a complicated sequence of decisions, but the recursive structure reveals itself the moment you ask: “what is the very last thing I’d need to do to complete the puzzle?” The largest disk must end up at the bottom of peg C — and for that, the n-1 smaller disks must all be on peg B (out of the way), the largest disk moves from A to C, and then the n-1 disks move from B to C. Each of those “move n-1 disks” steps is exactly the same problem, one size smaller:

#include <stdio.h>

void hanoi(int n, char from, char aux, char to) {
    if (n == 0) return;                          /* base case: nothing to move */
    hanoi(n - 1, from, to, aux);                 /* move n-1 disks out of the way */
    printf("Move disk %d from %c to %c\n", n, from, to);
    hanoi(n - 1, aux, from, to);                 /* move n-1 disks onto the destination */
}

Three lines of code (excluding the base case and print). Try hanoi(3, 'A', 'B', 'C') by hand and verify every move is legal — the recursive description and the physical constraint are the same statement, viewed from two different angles.

The cost: the recurrence is T(n) = 2T(n-1) + O(1) — move n-1 disks twice, plus one O(1) disk move. Unrolling: T(n) = 2ⁿ - 1 moves. This is provably optimal — you cannot move n disks in fewer moves — and it is Θ(2ⁿ). For n = 64 disks (the legendary temple legend), that is 2⁶⁴ - 1 ≈ 1.8 × 10¹⁹ moves. At one move per second, that is about 585 billion years — safely longer than the current age of the universe.

Pause and think: The Tower of Hanoi recurrence T(n) = 2T(n-1) + 1 shrinks the problem by one each level rather than by half, and the branching factor is 2. Contrast this with merge sort: T(n) = 2T(n/2) + n — also branches in 2, but shrinks by half. That one difference — “halving” vs “by one” — turns Θ(n log n) into Θ(2ⁿ). Recursive problems that shrink by a constant amount per level instead of by a constant factor are almost always exponential — and recognizing that shape on sight, before you run any code, is one of the most practically useful pattern-recognition skills in this entire chapter.

Recursion Trees and the Cost of Branching

factorial makes exactly one recursive call per invocation — a linear chain. Many recursive algorithms make multiple recursive calls, and that branching changes the cost analysis dramatically. The textbook example is the naive recursive Fibonacci function:

long long fib(int n) {
    if (n < 2) {
        return n;                           /* base cases: fib(0) = 0, fib(1) = 1 */
    }
    return fib(n - 1) + fib(n - 2);         /* two recursive calls */
}

Draw out the calls made by fib(5) as a tree — fib(5) calls fib(4) and fib(3); fib(4) calls fib(3) and fib(2); and so on — and something troubling becomes visible almost immediately: fib(3) is computed twice. fib(2) is computed three times. The tree branches every level, and the same sub-problems reappear over and over, deeper and deeper down. Counting carefully, the total number of calls roughly doubles with each increment of n, giving a running time of O(2ⁿ) — exponential, despite the fact that there are only n + 1 distinct sub-problems to solve.

Pause and think: This is your first concrete encounter with a pattern that will become the centerpiece of an entire later chapter: a recursive structure with overlapping sub-problems, solved naively by recomputing each one from scratch every time it’s needed. Sit with the discomfort of that wasted work for a moment — “I already calculated that two branches ago!” — because the entire idea of dynamic programming is born from exactly that feeling, formalized into a discipline: remember what you’ve already computed, and look it up instead of redoing it. Keep this fib example in your pocket; we will return to it and fix it properly.

This also illustrates a crucial lesson in reading recursive code for complexity: counting recursive calls, not just lines of code, is the key skill. A two-line function can hide an exponential explosion; a much longer-looking function with a single, shrinking recursive call can be perfectly efficient.

Divide and Conquer: A Design Recipe

Divide and conquer is a strategy for designing algorithms — a recipe you can apply deliberately, not just a pattern you stumble into. It has three steps:

Divide — split the problem into smaller sub-problems of the same kind.
Conquer — solve each sub-problem recursively (with a base case for the smallest instances).
Combine — merge the sub-solutions into a solution for the original problem.

The strategy earns its keep when the combine step is cheap relative to the size of the problem it’s gluing back together — that’s what allows the whole construction to beat a brute-force approach. Two classic examples make this concrete:

Binary search divides a sorted array in half, conquers by recursing into the half that could contain the target, and combines… by doing nothing at all (the answer to the sub-problem is the answer to the whole problem):

int binary_search(const int arr[], int lo, int hi, int target) {
    if (lo > hi) {
        return -1;                              /* base case: empty range, not found */
    }
    int mid = lo + (hi - lo) / 2;               /* avoids overflow vs. (lo + hi) / 2 */
    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] < target) {
        return binary_search(arr, mid + 1, hi, target);
    } else {
        return binary_search(arr, lo, mid - 1, target);
    }
}

Merge sort divides an array into two halves, conquers by recursively sorting each half, and combines by merging two sorted halves into one sorted whole — an O(n) operation that is the engine driving the entire algorithm’s efficiency (we dissect it fully, including the merge step, in the Sorting Algorithms chapter):

void merge_sort(int arr[], int lo, int hi) {
    if (lo >= hi) {
        return;                                  /* base case: 0 or 1 elements, already sorted */
    }
    int mid = lo + (hi - lo) / 2;
    merge_sort(arr, lo, mid);                    /* conquer: sort left half */
    merge_sort(arr, mid + 1, hi);                /* conquer: sort right half */
    merge(arr, lo, mid, hi);                     /* combine: merge the two sorted halves */
}

Notice the family resemblance: both functions shrink the problem by (roughly) half and recurse. The difference that matters most for performance is the cost of combining — O(1) for binary search versus O(n) for merge sort — and that single difference is what separates an O(log n) algorithm from an O(n log n) one, as we’re about to see precisely.

Recurrence Relations: Writing Down the Cost of Recursion

To analyze a recursive algorithm’s running time, you write a recurrence relation — an equation that expresses T(n), the time to solve a problem of size n, in terms of T applied to smaller sizes, plus the cost of the non-recursive work at this level. Reading the divide-and-conquer recipe straight off the code gives you the recurrence almost for free:

Binary search: one recursive call on a problem half the size, plus O(1) work to decide which half. T(n) = T(n/2) + O(1).
Merge sort: two recursive calls, each on a problem half the size, plus O(n) work to merge. T(n) = 2T(n/2) + O(n).
Naive Fibonacci: two recursive calls, each on a problem only one smaller (not half!), plus O(1) work to add. T(n) = T(n-1) + T(n-2) + O(1).

Writing the recurrence is the easy part. Solving it — finding a closed-form Big-O expression — is where the insight lives. There are two complementary ways to do it.

Method 1: The Recursion Tree

Draw the recursion as a tree, where each node represents one call and is labeled with the amount of non-recursive work it does. Then sum the work level by level.

For merge sort, T(n) = 2T(n/2) + O(n): the root does O(n) work and has 2 children, each handling a problem of size n/2 and doing O(n/2) work — so each level of the tree does a total of O(n) work (two nodes doing n/2 each, four nodes doing n/4 each, and so on — it’s always n in total). The tree has O(log n) levels, because the problem size halves at each level until it reaches the base case. Total cost: (work per level) × (number of levels) = O(n) × O(log n) = O(n log n).

For binary search, T(n) = T(n/2) + O(1): there’s only one branch per level, doing O(1) work, and O(log n) levels. Total cost: O(1) × O(log n) = O(log n).

Try it yourself: Use the recursion-tree method on the Tower of Hanoi recurrence, T(n) = 2T(n - 1) + O(1) (move n - 1 disks out of the way, move the largest disk, move the n - 1 disks back on top). Notice that the problem shrinks by one each time rather than by half — which means the tree has O(n) levels, not O(log n), and the number of nodes doubles at every one of those n levels. Work out the total. (If you’ve heard the legend of the temple monks moving 64 golden disks one at a time, and wondered why it would supposedly take longer than the age of the universe — this calculation is the entire explanation.)

Method 2: The Master Theorem

The recursion tree method always works, but redrawing a tree every time is tedious. The Master Theorem packages the result of that method into a reusable formula for the extremely common shape T(n) = a·T(n/b) + f(n), where a is the number of recursive calls, n/b is the size of each sub-problem, and f(n) is the cost of the non-recursive (divide + combine) work. Compare f(n) to n^(log_b a) — the amount of work that would be done if the combine step were free and only the sheer number of leaf calls mattered:

If f(n) grows slower than n^(log_b a), the leaves dominate the total cost: T(n) = Θ(n^(log_b a)).
If f(n) grows at the same rate as n^(log_b a), every level contributes equally, and there are Θ(log n) levels: T(n) = Θ(n^(log_b a) · log n).
If f(n) grows faster than n^(log_b a) (and a mild technical condition holds), the root dominates: T(n) = Θ(f(n)).

Apply it to merge sort: a = 2, b = 2, so n^(log_b a) = n^(log₂ 2) = n¹ = n. The combine cost f(n) = Θ(n) grows at the same rate — the middle case applies, giving T(n) = Θ(n log n). Apply it to binary search: a = 1, b = 2, so n^(log_b a) = n^(log₂ 1) = n⁰ = 1. The non-recursive cost f(n) = Θ(1) again matches — middle case again — giving T(n) = Θ(1 · log n) = Θ(log n). Both answers match what the recursion-tree method told us, because the Master Theorem is the recursion-tree method, pre-solved for this common shape. (It does not apply to every recurrence — the Fibonacci recurrence T(n) = T(n-1) + T(n-2) + O(1) has a different shape entirely, and needs other techniques, which is one reason the recursion-tree method remains valuable as a fallback that always works.)

A Worked Design Problem: Maximum Subarray

Theory is one thing; designing a divide-and-conquer algorithm from scratch is another, and it’s the skill this chapter is really after. Here is a problem that rewards careful thought: given an array of integers (possibly negative), find the contiguous subarray with the largest sum. For example, in [-2, 1, -3, 4, -1, 2, 1, -5, 4], the answer is the subarray [4, -1, 2, 1], with sum 6.

The brute-force approach checks every possible subarray — O(n²) or O(n³) depending on how naively you compute the sums. Can divide and conquer do better? Split the array into a left half and a right half. The maximum subarray either:

lies entirely within the left half, or
lies entirely within the right half, or
straddles the midpoint — and this is the case that makes the problem interesting.

Cases 1 and 2 are solved by recursion — the same problem, on a half-sized input. Case 3 cannot be solved recursively, because a subarray that crosses the midpoint isn’t “entirely within” either recursive sub-problem; it has to be found directly. But it can be found in O(n) time with a small, sharp insight: any subarray crossing the midpoint consists of some suffix of the left half glued to some prefix of the right half — and the best such suffix and the best such prefix can each be found independently with a single linear scan outward from the midpoint, then added together.

Try it yourself, before reading further: Try to write the function that finds the best “crossing” subarray sum, given the midpoint. Resist the urge to compare every suffix against every prefix (that reintroduces an O(n²) cost into the combine step, which would defeat the entire point). What’s the minimum information you need to remember as you scan outward from the midpoint in each direction?

/* Returns the maximum sum of a subarray that crosses index `mid`. */
int max_crossing_sum(const int arr[], int lo, int mid, int hi) {
    int left_sum = INT_MIN, sum = 0;
    for (int i = mid; i >= lo; i--) {            /* scan left, extending the suffix */
        sum += arr[i];
        if (sum > left_sum) left_sum = sum;
    }

    int right_sum = INT_MIN;
    sum = 0;
    for (int i = mid + 1; i <= hi; i++) {        /* scan right, extending the prefix */
        sum += arr[i];
        if (sum > right_sum) right_sum = sum;
    }

    return left_sum + right_sum;                 /* best suffix + best prefix, glued at mid */
}

int max_subarray_sum(const int arr[], int lo, int hi) {
    if (lo == hi) {
        return arr[lo];                           /* base case: one element */
    }
    int mid = lo + (hi - lo) / 2;
    int left  = max_subarray_sum(arr, lo, mid);
    int right = max_subarray_sum(arr, mid + 1, hi);
    int cross = max_crossing_sum(arr, lo, mid, hi);

    int best = (left > right) ? left : right;
    return (cross > best) ? cross : best;         /* take the best of all three cases */
}

The recurrence is T(n) = 2T(n/2) + O(n) — exactly merge sort’s shape — so by the Master Theorem (or the recursion tree, if you’d rather draw it out and confirm), this runs in O(n log n). That’s a real, substantial improvement over the brute-force O(n²), achieved purely through a smarter decomposition of the problem.

Pause and think: It turns out there is an even faster, O(n) algorithm for this exact problem (Kadane’s algorithm — a single linear scan, with no recursion at all), which you’ll encounter as a beautiful illustration of dynamic programming later in this course. That should reframe how you think about the divide-and-conquer solution above: it isn’t “the” answer, it’s “an” answer — a genuine improvement over brute force, arrived at through a disciplined design process, but not necessarily the ceiling of what’s possible. Holding two solutions to the same problem in your head simultaneously — one you’ve derived, one you suspect exists but haven’t found yet — is exactly the tension that drives algorithm design forward. Don’t stop asking “can I do better?” the moment you find an answer that works.

Backtracking: Recursion That Knows When to Give Up

Backtracking is a refinement of plain recursive search, suited to problems where you build a solution incrementally — piece by piece — and at each step you have several choices to try. The key idea: try a choice, recurse to extend the partial solution, and if that path turns out to be a dead end, undo the choice (“backtrack”) and try the next one. It is systematic trial and error, with the crucial property that you prune a branch — abandon it without further exploration — the instant you can prove it cannot lead anywhere good.

The textbook showcase is the N-Queens problem: place N queens on an N×N chessboard so that no two attack each other (no two share a row, column, or diagonal). Brute force would try every way to place N queens on N² squares — astronomically expensive. The first good idea that tames this: since no two queens can share a row, just decide which column each row’s queen goes in — one queen per row, by construction. That alone collapses the search space from “choose N of N² squares” down to “choose one column for each of N rows”:

#include <stdbool.h>
#include <stdlib.h>

bool is_safe(const int columns[], int row, int col) {
    for (int prev_row = 0; prev_row < row; prev_row++) {
        int prev_col = columns[prev_row];
        if (prev_col == col ||                                /* same column */
            abs(prev_col - col) == abs(prev_row - row)) {     /* same diagonal */
            return false;
        }
    }
    return true;
}

bool place_queens(int columns[], int row, int n) {
    if (row == n) {
        return true;                       /* every row has a safely placed queen: done */
    }
    for (int col = 0; col < n; col++) {
        if (is_safe(columns, row, col)) {
            columns[row] = col;            /* make a choice */
            if (place_queens(columns, row + 1, n)) {
                return true;               /* it led to a full solution: keep it */
            }
            /* otherwise: implicitly undo by overwriting columns[row] on the next iteration —
               this loop trying the next column *is* the "backtrack" step */
        }
    }
    return false;                          /* no column in this row works: report failure upward */
}

Look closely at where the power comes from: is_safe is checked before recursing, not after a complete board is built and found to be invalid. This is pruning — the moment a partial placement is doomed, the algorithm abandons it and moves on, without ever exploring the (potentially enormous) space of completions that share that doomed prefix. The difference between “generate every complete arrangement, then filter” and “stop building the moment you know it’s hopeless” is often the difference between an algorithm that finishes in milliseconds and one that doesn’t finish in your lifetime.

Try it yourself: Backtracking is the natural strategy for an entire family of problems that share the shape “build a solution piece by piece, with constraints that can be checked early.” Pick one of these and sketch — in pseudocode, on paper — what the “choice,” the “safety check,” and the “base case” would be: (a) finding a Hamiltonian cycle in a graph (a path that visits every vertex exactly once and returns to the start), (b) the subset-sum problem (does some subset of a given set of numbers add up to exactly a target value?), (c) solving a Sudoku puzzle. In each case, ask yourself: what’s the cheapest possible check that lets me abandon a branch as early as possible? That question — “how early can I detect failure?” — is the entire art of writing backtracking algorithms that are fast in practice, even when their worst-case complexity remains exponential.

Bringing It Together: Practice as a Problem-Solver

Trace it by hand. Write out, level by level, every call made by fib(6) (there are 25 of them). Circle the calls that compute the same value as some earlier call. What fraction of the total work is redundant? How does that fraction change as n grows — and what does that tell you about how badly the exponential blowup compounds?
Write the recurrence, then solve it. For each of the following, write down T(n) as a recurrence relation, and then find its Big-O class (using the recursion tree, the Master Theorem, or both, and noting which apply): (a) a function that recursively searches a binary tree by checking the current node and then recursing into both children, doing O(1) work per node; (b) a function that splits an array into three equal parts, recurses on each, and combines them in O(n) time; (c) a function that recurses on an array with its last element removed, doing O(n) work (e.g. a linear scan) at each step before recursing.
Design challenge — convert brute force into divide and conquer. Given two n-digit numbers, the standard “long multiplication” you learned in school takes O(n²) single-digit multiplications. Karatsuba’s algorithm splits each number into a high half and a low half, and through a clever algebraic rearrangement, computes the product using only three recursive multiplications of n/2-digit numbers (rather than the four you’d get from naively multiplying each half by each half), plus O(n) extra additions and shifts. Without looking up the algebra: write down the recurrence this description implies, and use the Master Theorem to work out what running time it achieves. Then ask yourself — does going from four recursive calls to three feel like it should matter that much? Compute both answers and see by how much it does. (This is a vivid lesson in just how sensitive recursive running times are to the constant a in T(n) = a·T(n/b) + f(n) — shaving one recursive call off a divide-and-conquer algorithm can be the difference between a merely good algorithm and a landmark one.)
Reflection. You’ve now seen three different “shapes” of recursion in this chapter: a single shrinking call (factorial, binary_search), a fixed number of calls on equally-sized sub-problems (merge_sort, max_subarray_sum), and a variable, pruned branching search (place_queens). For each, write one sentence describing the kind of problem it’s suited to. Then, the next time you face a new problem and instinctively reach for recursion, use those three sentences as a checklist — which shape does this problem actually have, and does your draft solution match it?