Divide and conquer

Divide, solve, combine

Divide and conquer breaks a problem into smaller instances, solves them, and combines their answers. A base case handles an instance small enough to answer directly. The subproblems must shrink, and the combination must preserve the meaning of the original task.

Unlike dynamic programming, ordinary divide and conquer often solves mostly independent subproblems. When subproblems overlap heavily, storing their results can be necessary. The distinction is about the structure of the work, not whether the code contains recursion.

A complete example

Find the maximum value in a nonempty list by dividing its index range.

values = [7, 2, 9, 4, 6]

def maximum(left, right):
    if right - left == 1:
        return values[left]
    middle = (left + right) // 2
    a = maximum(left, middle)
    b = maximum(middle, right)
    return max(a, b)

print(maximum(0, len(values)))

9

The range includes left and excludes right. A one-element range returns that element. Otherwise the midpoint divides the range into two nonempty parts. The largest value of the whole range is the larger of the two returned values.

Every element appears in one base case. Combining each pair requires constant work, so the total time is O(n). The call depth is O(log n) because the ranges are split roughly in half. This example is a teaching exercise: Python's built-in max is simpler when the task is only to find a maximum.

Quicksort

The sorting exercise uses a pivot. Partition values into those smaller than the pivot, equal to it, and larger than it. Recursively sort the smaller and larger groups, then concatenate the three groups. Keeping equal values separately ensures that repeated values do not create a nonshrinking recursive call.

For a readable first implementation, new lists make the partition clear. The total extra space can be O(n) for balanced recursion, with additional allocation work. An in-place implementation has different bookkeeping and is not required to understand the partition idea.

Pivot choice affects performance. Balanced splits give O(n log n) work. Repeatedly splitting off only one element gives O(n squared) work and deep recursion. A first-element pivot on an already sorted list is a classic failure. The exercise allows at most 1,000 values, but this is still enough to expose Python recursion-depth trouble.

Using a middle element as the pivot avoids that particular sorted-input failure. It does not guarantee balanced partitions for every possible input. Test sorted, reverse-sorted, and all-equal values and understand the remaining worst case.

Tiling and overlapping work

The second exercise asks for tilings using lengths one, two, and three. Classify a tiling by its first tile, then solve the remaining length. The empty board has one tiling, and a negative length has none.

Different branches can request the same remaining length. A direct recursive version demonstrates the decomposition but repeats work. Its input limit is small. The dynamic-programming version elsewhere in the path raises the limit and requires storing answers. Compare the call tree with a table to see exactly what is reused.

Practice and common mistakes

Write down the range convention and keep it consistent. An excluded right endpoint means a length of right - left, not right - left + 1. Check that both recursive calls are strictly smaller. Check duplicate values when partitioning.

For sorting, verify that output is nondecreasing and contains every input value with the same multiplicity. A sorted list that accidentally drops duplicates is still wrong. For counting, make sure cases are disjoint before adding their answers.

Finish by explaining the base case, the split, the combination, and the worst-case cost of your program. Those four decisions turn recursive code into an algorithm you can justify.