One smaller instance, not many
Decrease and conquer reduces a problem to a single smaller instance, solves that, and extends its solution to the original. It differs from divide and conquer, which splits into several subproblems. Insertion sort is a clean example: sort the first n minus one elements, then insert the last one into place.
Three common flavors
The amount you decrease by gives the technique its character:
- Decrease by a constant: shrink by one each step, as in insertion sort or computing a factorial.
- Decrease by a constant factor: shrink by, say, half each step, as in binary search.
- Decrease by a variable amount: the reduction depends on the data, as in the Euclidean algorithm for the greatest common divisor.
Why it is worth naming
Because only one subproblem remains, there is no combine step that merges multiple answers; you simply adjust the smaller solution. This often yields simpler code than full divide and conquer, and the decrease by factor variant explains why halving searches are so fast: each step throws away a constant fraction of the remaining work.
Key idea
Decrease and conquer reduces a problem to a single smaller instance and extends its solution, decreasing by a constant, by a factor, or by a variable amount, with no multi way combine step.