演算法-資料結構學習筆記 Recursions 遞迴

什麼是遞迴？

遞迴是藉由重複執行某一小部分的程式碼，並且不斷變更執行的環境或參數值，直到程式碼達到某一個終結的條件，或是成功達成特定目標，並且跳脫重複執行的迴圈。

以實務上來說，通常這一小部分程式碼會是一個函式，而遞迴即是該函式於內部再次呼叫自身，達到不斷重複執行的過程。

因此，從遞迴包含了兩個非常重要的組成，一個是不斷重複執行的過程中需要改變參數，另一個則是跳脫重複執行的終止條件。

第一個組成條件相當好理解，因為要藉由遞迴來重複執行函式達成特定目的時，需要在每一次的執行都代入不同的參數，才會產生不同的結果或輸出，否則一直代入同樣的參數重複執行同一個函式，不管執行再多次也不會有任何改變。

第二個組成條件則是終止條件，也是遞迴中非常重要的觀念。但是在了解為何需要設計跳脫重複執行的終止條件時，要先知道所謂的 Call stack。在 JS 中，當執行一個新的函式時，JS 就會在 Call stack 頂部加上該函式，直到函式執行完畢，才會將其從頂部移除。

因此，今天在使用遞迴的時候，由於遞迴和迴圈最大的差別就在於，前者是藉由不斷呼叫自己的方式來達到重複執行的過程，因此 Call stack 就會一直往上疊加新執行的函式，假設遞迴的終止條件設計不良，最終就會因為超出記憶體負荷而導致 Stack oveflow( 不是那個工程師交友平台 XD )，其危險性甚至比無窮迴圈還可怕喔！

來實作一個遞迴吧！

假設今天要實作一個倒數計時器，函式會接受一個數字參數，並從該數字往下倒數至 0，可以分別用 for 迴圈和遞迴來實作，看看差別在哪。

for 迴圈版

function countDown(num) {
  for (let i = num; i >= 0; i--) {
    console.log(i)
  }
}

遞迴版

function countDown(num) {
  // base case
  if (num === 0) {
    console.log(num)
    return
  }
  
  console.log(num)
  num--
  // call itself
  countDown(num)
}

從上面兩個版本可以知道，for 迴圈版只會執行一次 countDown() 函式，並在函式內依據代入的參數執行相對應的迴圈次數；而遞迴版則是依據最初代入的參數，執行相對應次數的函式，但需要設計一個數字為 0 即終止執行的條件，否則就會不斷呼叫，直到發生 stack overflow，好孩子千萬別輕易嘗試 XD

遞迴的常見錯誤

1. 忘記或設計不良的終止條件

如果今天遞迴發生了 stack oveflow 的錯誤，往往是因為忘記寫終止條件，或著是終止條件設計不良，導致函式即使不斷重複執行，也永遠無法達到終止條件。

2. 忘記使用 return 回傳呼叫自身，或是回傳了錯誤的數值

以上述倒數計時器的函式為例，如果今天忘記在每一次執行後將參數減一，或是傳入錯誤的參數給再次自呼叫的函式，那即使終止條件設置妥當，也會因為回傳了錯誤的參數而導致無法達到終止條件。

參考資料

https://www.udemy.com/course/js-algorithms-and-data-structures-masterclass/