decrease and conquer

Divide and conquer breaks a problem into several subproblems and solves them all. Decrease and conquer is its leaner cousin: it reduces the problem to just ONE smaller instance, solves that, and extends the answer. Climbing a staircase is the picture — to reach step n you only need to have reached step n-1 and then take one more step; there is no second branch to also climb.

There are three flavours by how much you shrink. Decrease by a constant: each step removes a fixed amount, as in insertion sort (sort the first n-1 elements, then insert the n-th) or computing x^n as x times x^(n-1). Decrease by a constant factor: each step throws away a fixed proportion, as in binary search (halve the range each time) or fast exponentiation (x^n from x^(n/2) squared) — these give O(log n) behaviour. Decrease by a variable amount: the shrink size depends on the data, as in Euclid's gcd, where gcd(a,b) reduces to gcd(b, a mod b). In every case there is a single recursive call, so the recurrence has the form T(n) = T(smaller) + work, with no branching factor a > 1.

Naming decrease and conquer separately is useful because the single-branch recursion behaves very differently from true divide and conquer: with one subproblem there is no merging of multiple answers, the recursion is a chain rather than a tree, and it often unrolls into a simple loop. Binary search is sometimes called divide and conquer, but it is more honestly decrease and conquer — it divides the array conceptually but conquers only one of the two halves. Recognizing this tells you to expect a thin recursion (linear or logarithmic depth) rather than the branching tree that produces n log n.