跳至主要内容

[演算法] 遞回函式(recursive function, recursion)

此系列筆記主要依照 [Udemy] Learning Algorithms in JavaScript from Scratch by Eric Traub 的課程脈絡加以整理,但部分程式碼是消化後以自己較易理解的方式重新撰寫,因此和原課程內容有些出入。

什麼是遞回函式(recursion)

遞回函式(recursive function)簡單來說就是在一個函式當中再去呼叫它自己,舉例來說會像這樣:

function recursive() {
if (/*...*/) {
return something;
} else {
// recursive case
recursive()
};
}

其中一個實際的範例就是階層的計算(factorial),階層聽起來可能很陌生,但是大家高中數學一定接觸過,例如 5! = 5 x 4 x 3 x 2 x 1。

演算法實做

透過遞回函式來實做一個階層(!)的函式:

function factorial(num) {
if (num === 1) {
return num;
} else {
return num * factorial(num - 1);
}
}
factorial(5); // 120

可以看到,當 num 不等於 1 的時候,它會去呼叫自己(return num * factorial(num-1),如果 num 等於 1 時,才會回傳結果。

因此實際上執行的過程會像這樣(call stack):

Learning Algorithms in JavaScript from Scratch

圖片來源:Learning Algorithms in JavaScript from Scratch by Eric Traub @ Udemy

觀念

之所以能夠透過遞回函式,是因為函式堆疊(stack)在執行時有一個特性,當某個函式呼叫另一個函式時,需要等到裡面的函式執行完產生結果後,才會繼續回來執行自己的函式內容,而這樣的情況也被稱作 後進先出(Last in First Out, LIFO) ,例如:

function last() {
console.log('後來才進堆疊');
}

function first() {
console.log('先進堆疊 - start');
last();
console.log('先進堆疊 - end');
}

first(); // "先進堆疊 - start" -> "後來進堆疊" -> "先進堆疊 - end"

algorithm: recursive function @ repl.it

也就是說,當我們在 first() 裡呼叫 last() 時,需要等 last() 執行完後,才會回到 first() 繼續執行。

另外,在寫遞回函式的時候一定記得設定終止條件,否則很容易跳不出來,導致無窮迴圈的情況產生。

資料來源