[演算法] 遞回函式（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 時，才會回傳結果。

因此實際上執行的過程會像這樣：

圖片來源：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