iT邦幫忙

2021 iThome 鐵人賽

DAY 8
0
自我挑戰組

30天不怕演算法:白話文版系列 第 8

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。

上一篇
Day 07:泡沫排序(bubble sort)
下一篇
Day 09:遞迴(2)
系列文
30天不怕演算法:白話文版30

尚未有邦友留言

立即登入留言