Recursion & Divide and Conquer

At a glance

The instinct

Look for self-similarity: the problem on a big input is the same problem on smaller inputs plus a little glue. Merge Two Sorted Lists is "pick the smaller head, then merge the rest". Pow(x, n) is "square the answer for n/2". Sort List is merge sort on a linked list. Reverse Pairs is merge sort with a counting step slipped in while both halves are sorted.

The skill is the leap of faith: assume your function already works on anything smaller, and only think about two things - the smallest case you can answer directly, and how to combine sub-answers.

Recognise it

Not this pattern if...

• Subproblems overlap heavily (Fibonacci, grid paths) - add memoisation and you are in DP territory.
• You must enumerate every choice and undo it - that is backtracking.
• You discard one half entirely using a yes/no test - that is binary search (a one-sided divide and conquer).
• Depth could reach 10^5 on a skewed structure - Java's default stack may overflow; go iterative.

Memory hack

Analogy - the exam-paper manager. A teacher with 400 unsorted exam papers hands 200 to each of two assistants and says "sort these". She does not care how they do it. When both piles come back sorted, she merges them by repeatedly taking the smaller top sheet. Each assistant secretly does the same thing with two helpers of their own, until someone holds one paper - which is already sorted.

Say it out loud:

1. "Base case: the smallest input I can answer directly is ___."
2. "I split into ___ and assume the recursive call returns the right answer for each part."
3. "Combine: given the sub-answers, the full answer is ___, costing ___, so T(n) = a·T(n/b) + f(n)."

How it works

Merge sort on [5, 2, 4, 1]: the arrows going down split, the merges coming back up do the real work.

flowchart TD
  A["[5, 2, 4, 1]"] --> B["[5, 2]"]
  A --> C["[4, 1]"]
  B --> D["[5]"]
  B --> E["[2]"]
  C --> F["[4]"]
  C --> G["[1]"]
  D --> H["merge: [2, 5]"]
  E --> H
  F --> I["merge: [1, 4]"]
  G --> I
  H --> J["merge: [1, 2, 4, 5]"]
  I --> J

To get the cost, write the recurrence and compare the work done by the subcalls with the combine step:

Java template

class DivideAndConquerTemplate {
    // Shape: solve(range) = combine(solve(left half), solve(right half)). Range is [lo, hi).
    static long solve(int[] a, int lo, int hi) {
        if (hi - lo <= 1) return 0;                 // base case: smallest input answered directly
        int mid = lo + (hi - lo) / 2;
        long left = solve(a, lo, mid);              // leap of faith
        long right = solve(a, mid, hi);
        return left + right + combine(a, lo, mid, hi);
    }

    // Example combine (Reverse Pairs): count cross pairs a[i] > 2*a[j], then merge the sorted halves.
    static long combine(int[] a, int lo, int mid, int hi) {
        long count = 0;
        for (int i = lo, j = mid; i < mid; i++) {   // both halves are sorted at this point
            while (j < hi && (long) a[i] > 2L * a[j]) j++;
            count += j - mid;
        }
        int[] merged = new int[hi - lo];
        int i = lo, j = mid, k = 0;
        while (i < mid || j < hi) {
            if (j == hi || (i < mid && a[i] <= a[j])) merged[k++] = a[i++];
            else merged[k++] = a[j++];
        }
        System.arraycopy(merged, 0, a, lo, merged.length);
        return count;
    }

    // Halving recursion: x^n in O(log n). n is long so that -Integer.MIN_VALUE does not overflow.
    static double pow(double x, long n) {
        if (n < 0) return 1 / pow(x, -n);
        if (n == 0) return 1;
        double half = pow(x, n / 2);                // ONE recursive call, reused twice
        return (n % 2 == 0) ? half * half : half * half * x;
    }
}

Complexity

• Time: read it from the recurrence (table above). Balanced halving with a linear combine is O(n log n); halving with constant work is O(log n).
• Space: recursion depth is O(log n) for balanced splits but O(n) for lopsided ones (e.g. a sorted input to Maximum Binary Tree), plus any merge buffers - O(n) for array merge sort.
• Linked-list merge sort needs no buffer; the top-down version still uses O(log n) stack.

Variations

• Linear recursion on lists - handle the head, recurse on the rest. Merge Two Sorted Lists.
• Halve and reuse - compute the half answer once and square it. Pow(x, n).
• Merge-based - sort halves, then merge (and count across the boundary). Sort List, Reverse Pairs.
• Build a tree from a range - pick the root, recurse on each side. Convert Sorted List to Binary Search Tree, Maximum Binary Tree.
• Spatial split - divide a grid into quadrants until uniform. Construct Quad Tree.
• Structural recursion on nested input - recurse on each bracket group (or simulate with stacks). Decode String.

Common mistakes

• Missing or incomplete base cases (empty input, single element, n == 0) - the result is a StackOverflowError.
• Splits that do not shrink: recursing on [lo, mid] when mid can equal hi repeats the same call forever.
• Forgetting to cut a linked list in half (slow.next = null) before recursing on each part.
• Computing 2 * nums[j] in int for cross counts - it overflows for values near 2^31; cast to long.
• Negating Integer.MIN_VALUE in Pow(x, n): -n is still negative. Widen to long first.

All practice problems

8 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.