Divide and conquer splits a problem into independent smaller problems of the same kind, solves each recursively and combines the answers.

Three steps

  1. Divide: split the problem (usually into two halves).
  2. Conquer: solve each part recursively; the smallest part (the base case) is solved directly.
  3. Combine: build the overall answer from the parts' answers.

The parts do not overlap, which separates this approach from dynamic programming, where subproblems repeat.

Recursion levels of merge sort: each level costs n, with log n levels
Recursion levels of merge sort: each level costs n, with log n levels

Example: recursive maximum

python
def max_rec(a, lo, hi):
    if lo == hi:                          # base case: one item
        return a[lo]
    mid = (lo + hi) // 2
    left = max_rec(a, lo, mid)            # solve the left half
    right = max_rec(a, mid + 1, hi)       # solve the right half
    return max(left, right)               # combine

data = [3, 9, 2, 7, 5, 8]
print(max_rec(data, 0, len(data) - 1))

The recurrence is T(n) = 2T(n/2) + O(1), so the cost is O(n), the same as a plain loop. The example only shows the pattern.

Fast exponentiation