Day 08：分治法与递回(1)

再继续写其他更快的排序演算法之前，先来写分治法(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。