再繼續寫其他更快的排序演算法之前，先來寫分治法(divide-and-conquer paradigm)，因為後面的演算法跟它大有關係。

分治法是一種演算法設計模式(design paradigm)，也就是說它並不是指特定一種演算法，而是一類演算法的框架或設計基礎。

divide-and-conquer這個名稱很直接地點出這類演算法的特性，也就是將大問題分解成小問題，小問題解決後，整個大問題也可以解決。中文叫做分治法也是同樣的意思，指將問題「分而治之」。這個手法對於解決龐大複雜的問題常有很好的效果，也才會成為許多演算法的基礎。

具體來說分治法有三個步驟：

1. 分解：將原問題分解成形式相同的子問題。
2. 解決：子問題小到可以直接解決就解決，否則用遞迴的方式解決子問題。
3. 合併：將子問題的解合併，成為原問題的解。

這裡講到分治法的一個核心—遞迴，那遞迴是什麼呢？

電腦科學中，遞迴是指一個函式呼叫自己的行為。分治演算法就是利用遞迴這個手段來不斷分解問題，問題分解到最後就可以毫不費力地解開，整體的答案當然也就呼之欲出。

舉一個例子，就會發現我們對遞迴的效果其實不陌生，只是可能更常用其他方法完成。

假設今天我們想要像跨年倒數讀秒一樣，顯示10到1的每個數字。
我們想到的做法可能是迴圈，例如while loop，

let n = 10;
while(n > 0){
    console.log(n);
    n--;
}

或是for loop，

for(let i = 10; i > 0; i--){
    console.log(i);
}

以上兩種迴圈用不同方式設定迴圈的開始和結束，但其實都是將一組步驟重複特定次數，也就是它們都是以疊代(iteration)的方式完成任務。

同樣一件事，也可以想成如果一個函式它所做的事情就是「印出數字n」，那我們可以讓它不斷呼叫自己，並每次將n變小，也可以完成同樣的事情。

function countDown(n){
    console.log(n);
    countDown(n-1);
}

countDown()在函式中會呼叫自己，來解決比原問題n小的子問題n-1；countDown(n-1)在執行時又會再呼叫自己，解決更小的子問題。

但以此函式來執行countDown(10)，會出現錯誤。因為函式不知道什麼時候要停，所以這樣的跨年倒數就算數到負數，還是會無限倒數下去，很顯然跟預期不符。所以我們在遞迴的過程中，需要一個終止函式的方法。

遞迴情況與基本情況

遞迴函式一定會包含遞迴情況(recursive case)與基本情況(base case)。遞迴情況是指函式繼續呼叫自己；基本情況就是指函式停止再呼叫自己。有了這兩種情況的判斷，就可以避免函式陷入無限迴圈。

如果將跨年倒數的例子加入基本情況，會變成：

function countDown(n){
// base case
    if (n <= 0){
        return;
    } 
// recursive case
    console.log(n);
    countDown(n - 1);
}
countDonw(10);

用文字可以理解為，countDown(n)會不斷以遞迴的方式解決更小的子問題，直到達到n<=0，遞迴才會終止。

除了跨年倒數，我們很熟悉的二分搜尋也運用了遞迴的手法。[註1]

如果「二分搜尋」是一個函式，那要查一個單字的話，步驟可以寫成：

1. 對字典進行二分搜尋。
2. 如果字典只剩0頁，結束搜尋。
3. 若字在前面，對前半本進行二分搜尋。
4. 若字在後面，對後半本進行二分搜尋。

其中步驟2是基本情況，讓函式知道什麼時候停止。步驟3和步驟4就是繼續呼叫自己的遞迴情況，來解決越來越小的問題(搜尋較小本的字典)。

不過，儘管遞迴那麼簡單直覺，也並沒有改變我們已知的結果，第一次看到遞迴函式的感覺還是蠻衝擊的。

會覺得，明明少寫那麼多東西，為什麼還可以有一樣的效果？

或者，用遞迴函式比用迴圈「高級」嗎？什麼情況下要選擇用哪個？

下一回會試著回答這些問題。

• [註1]二分搜尋運用了遞迴，但嚴格說起來並不算是分治演算法，因為它是直接將原問題削減成小問題，並沒有「合併小問題的解作為原問題解」這個步驟。可以稱這樣的演算法為decrease-and-conquer algorithm。