今天開始認識 Recursion（遞迴），查了一下才發現，原來遞迴最基本的概念就是：函式在執行過程中再次呼叫自己。

但為什麼函式需要呼叫自己？

以前端來說，我們有時候會遇到不知道到底有幾層的資料。例如電商網站的商品分類可能是：

服飾 → 男裝 → 外套 → 皮衣

今天可能只有三層，之後也可能變成五層、六層。面對這種一層包一層，而且每一層處理方式都很類似的資料結構，就有機會使用遞迴來處理。

不過函式如果一直呼叫自己，不就永遠不會停嗎？

所以遞迴通常有兩個很重要的部分：

Base Case（基底條件）：遞迴的停止條件。當符合條件時，就不再繼續呼叫自己。

Recursive Case（遞迴情況）：還沒有到停止條件時，將問題縮小，再次呼叫自己。

我覺得可以用開車來理解這兩個概念。

Recursive Case 很像油門，而 Base Case 很像煞車。

當函式再次呼叫自己時，就像踩著油門繼續往前走；但我們不可能讓車子永遠往前開，所以必須設定一個「遇到紅燈就停下來」的條件，這個條件就是 Base Case。

如果只有 Recursive Case，卻沒有 Base Case，就像一直踩著油門卻完全沒有停下來的條件。函式會不斷呼叫自己，呼叫層數越來越深，最後可能超過執行環境允許的 Call Stack 範圍，造成 呼叫堆疊溢位（Stack Overflow）。

先來看一個簡單的例子

function foo(n) {
  if (n === 1) return 1;
  return n + foo(n - 1);
}

console.log(foo(3));

當執行 foo(3) 時，因為 3 !== 1，所以會執行：

return 3 + foo(2);

接著 foo(2) 又會呼叫 foo(1)：

return 2 + foo(1);

到了 foo(1) 時，終於符合 Base Case，因此直接 return 1，最後得到：

3 + 2 + 1 = 6

所以 console.log(foo(3)) 最後會印出 6。

不過這裡其實還有一個我今天先不深入的問題：

程式到底怎麼知道 foo(1) 結束之後，要回去繼續處理 foo(2)，最後再回到 foo(3)？

這就跟 Call Stack（呼叫堆疊） 有關，也是我下一篇準備繼續理解的內容。

自己試著寫一個 countdown

理解 Base Case 和 Recursive Case 之後，我試著自己寫一個簡單的倒數函式：

function countDown(num: number) {
  if (num === 0) {
    return '倒數結束'
  } else {
    return `倒數中 ${num} ${countDown(num - 1)}`
  }
}

console.log('開始設定 countDown 的數值 ', countDown(5))

這裡的 num === 0 就是 Base Case，當數字減到 0 時停止遞迴。

而 countDown(num - 1) 則是 Recursive Case，每次呼叫自己時都將數字減 1，讓 num 一步一步接近停止條件。

最後會得到：

倒數中 5 倒數中 4 倒數中 3 倒數中 2 倒數中 1 倒數結束

今天主要先理解一件事：

遞迴不是單純「函式一直呼叫自己」，而是要有一個停止條件，並且每次呼叫都讓問題逐漸接近這個停止條件。

參考資料

• HackMD，Recursion 相關筆記
  https://hackmd.io/g28x5uBVRrK7_wanRFx35Q

• Medium，〈資料結構與演算法 (4) — Recursion〉
  https://medium.com/on-my-way-coding/%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B%E8%88%87%E6%BC%94%E7%AE%97%E6%B3%95-4-recursion-fa7bb383957e

• iT 邦幫忙，Recursion 相關文章
  https://ithelp.ithome.com.tw/articles/10368680