---
tags: DSA in JavaScript
---
# Ch7. Recursion (遞迴)
定義：一個呼叫自己的函式

### Call Stack in JavaScript (背景知識)
Stack：一個後進先出的資料結構
* 當一個函式被觸發時，JS 引擎會將這個函式放到 Call Stack 裡面，直到函式結束(回傳值)後，才會從 Call Stack 裡面取出。
* 而遞迴會在執行過程中，把自己不斷地放入 Call Stack 。
* 一旦 Call Stack 超出一定數量後，就會跳出錯誤 `maximum call stack size exceeded`，也就是常見的 `stack overflow`。

### 在哪裡可以看到遞迴的例子？
- JSON.parse / JSON.stringify
- querySelector / getElementById / 其他搜尋 DOM 的其他方法
- 遍歷 object
- 使用較複雜的資料結構時 (tree, graph)
- 迴圈的另一個替代方案

### 遞迴函式的必備條件
遞迴是個雙面刃，提高函式重用性的同時，也要防範無窮迴圈與 Call Stack 的限制
必備條件都是避免無窮迴圈的應對措施
1. **Base Case**
必須要有跳脫條件(return)，避免不斷呼叫造成無窮迴圈
2. **Different Input**
每一次函式代入的參數必須與上一次不同

// 數學的階層概念 (4!)
function factorial(num) {
    if (num === 1) return 1 // 這個就是 base case，必須要有一個回傳值
    return num * factorial(num - 1)
}