[演算法] 遞回函式(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 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()
繼續執行。
另外,在寫遞回函式的時候一定記得設定終止條件,否則很容易跳不出來,導致無窮迴圈的情況產生。
資料來源
- Learning Algorithms in JavaScript from Scratch by Eric Traub @ Udemy
- 【演算】遞迴函式 - Recursive Function
- 堆疊 @ wikipedia