Divide and Conquer (recursion)

Divide and Conquer

Divide and conquer solves a problem by breaking it into smaller problems of the same kind, solving those subproblems, and combining their answers. Recursion is a natural way to express this pattern because the same function can solve each smaller instance.

Divide

Split the input into smaller, similar subproblems.

Conquer

Solve each subproblem recursively. A base case stops the recursion.

Combine

Build the original answer from the smaller answers.

Every correct recursive algorithm needs a base case that can be answered directly and a recursive step that moves strictly closer to that base case. Otherwise the recursion never ends.

Follow the three phases

Staircase problem

Suppose a staircase has \(n\) steps and we may climb either one or two steps at a time. Let \(W(n)\) be the number of different ways to reach the top. The final move came from step \(n-1\) or step \(n-2\), so the two disjoint sets of paths can be added.

\(W(n)=W(n-1)+W(n-2),\qquad W(0)=W(1)=1\)

The recurrence is Fibonacci-like. A direct recursive implementation mirrors the definition, but it recomputes the same values many times. Later, dynamic programming will show how to store those answers and reduce the runtime from exponential to linear.

Build the staircase recurrence

Stairs: 6

Grid paths

Now start in the top-left cell of a board and move only right or down. To enter any other cell, the last move must come from above or from the left. Therefore the number of paths to a cell is the sum of those two neighboring values. Cells in the first row and first column have one path.

\(P(r,c)=P(r-1,c)+P(r,c-1)\)

This example is recursive in structure even though the animation fills a table. The table makes overlapping subproblems visible: the same smaller path counts contribute to many later cells.

Count paths through the board

Rows Columns

Start

Finish

Merge Sort

Merge sort divides an array into two halves until every subarray contains at most one item. A one-item array is already sorted. During the combine phase, two sorted arrays are merged by repeatedly taking the smaller front value.

def merge_sort(values):
    if len(values) <= 1:
        return values

    middle = len(values) // 2
    left = merge_sort(values[:middle])
    right = merge_sort(values[middle:])
    return merge(left, right)

Splitting produces two subproblems of half the input size. Merging examines all \(n\) values. This gives the recurrence \(T(n)=2T(n/2)+\Theta(n)\), whose solution is \(\Theta(n\log n)\).

Divide: find the middle in constant time.
Conquer: recursively sort both halves.
Combine: merge both sorted halves in linear time.

Watch merge sort

Master theorem

The Master theorem solves many divide-and-conquer recurrences of the form below. Here \(a\) is the number of recursive subproblems, \(n/b\) is each subproblem's size, and \(\Theta(n^d)\) is the work performed outside the recursive calls.

\(T(n)=aT(n/b)+\Theta(n^d)\)

\(\log_b a<d\) \(\Theta(n^d)\)

The work near the root dominates.

\(\log_b a=d\) \(\Theta(n^d\log n)\)

Every level performs the same asymptotic work.

\(\log_b a>d\) \(\Theta(n^{\log_b a})\)

The many leaves dominate.

This is the common polynomial form of the theorem. To use it, identify \(a\), \(b\), and \(d\), calculate \(\log_b a\), compare it with \(d\), and select the matching case. More general versions require additional regularity conditions.

Explore a recurrence tree

\(a\) \(b\) \(d\)

Exercises

Use the animations above when you need a hint, then solve the short exercises below. New values can be generated repeatedly.

Exercise 1: Build a recurrence

A rabbit can advance by one or two tiles. Which recurrence counts the ways it can reach tile \(n\)?

Exercise 2: Apply the Master theorem

Exercise 3: Derive a recurrence

Count the recursive calls, determine the size of each subproblem, and then measure the work performed outside the recursive calls.