減治法（decrease and conquer）

分治法把一個問題拆成數個子問題並全部解決。減治法是它較精簡的表親：它把問題縮減成「一個」較小的實例，解出它，再延伸答案。爬樓梯就是這幅畫面——要到第 n 階，你只需先到第 n-1 階再踏一步；沒有第二條分支也要爬。

依縮減量有三種風味。常數減：每步移除固定量，如插入排序（先排前 n-1 個元素，再插入第 n 個）或把 x^n 算成 x 乘 x^(n-1)。常數倍率減：每步丟掉固定比例，如二分搜尋（每次把範圍減半）或快速冪（x^n 由 x^(n/2) 平方而來）——這些給出 O(log n) 的行為。變量減：縮減大小取決於資料，如歐幾里得的最大公因數，其中 gcd(a,b) 化簡為 gcd(b, a mod b)。每種情況都只有一次遞迴呼叫，所以遞迴關係式形如 T(n) = T(較小) + 工作量，沒有大於 1 的分支因子 a。

把減治法單獨命名是有用的，因為單分支遞迴的行為與真正的分治法很不一樣：只有一個子問題就沒有多個答案的合併，遞迴是一條鏈而非一棵樹，且常能展開成一個簡單迴圈。二分搜尋有時被稱為分治法，但更誠實地說它是減治法——它在概念上把陣列分開，卻只征服兩半中的一半。認清這點會讓你預期一個瘦的遞迴（線性或對數深度），而非那種產生 n log n 的分支樹。