2017年9月23日 星期六

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

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

什麼是遞回函式(recursion)

遞回函式(recursive function)簡單來說就是在一個函式當中再去呼叫它自己,其中一個實際的範例就是階層的計算(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)
  }
}
factorail(5)        // 120
可以看到,當 num 不等於 1 的時候,它會去呼叫自己(return num * factorial(num-1),如果 num 等於 1 時,才會回傳結果。
因此實際上執行的過程會像這樣:

觀念

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

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

first()    // "先進堆疊 - start" -> "後來進堆疊" -> "先進堆疊 - end"
也就是說,當我們在 first() 裡呼叫 last() 時,需要等 last() 執行完後,才會回到 first() 繼續執行。
另外,在寫遞回函式的時候一定記得設定終止條件,否則很容易跳不出來,導致無窮迴圈的情況產生。

資料來源

0 意見:

張貼留言