上一章學到遞迴（Recursion）會在函式裡面不斷呼叫自己，但我一直有個疑問：

函式被呼叫之後，不是馬上就會執行嗎？那為什麼還會有「堆疊」的現象？

我原本以為 Call Stack 是把「還沒執行的函式」放在記憶體裡排隊，後來才發現這個理解不太正確。

Call Stack 到底在 Stack 什麼？

當 JavaScript 呼叫一個函式時，會建立這次函式呼叫的執行資訊，並放進 Call Stack。

如果函式執行完畢，就會從 Stack 最上方移除；但如果函式還沒執行完，又呼叫了另一個函式，新的函式就會再疊到上面。

這也符合前面學過的 Stack：

後進先出（Last In, First Out，LIFO）。

例如昨天寫的 countDown：

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

console.log(countDown(3))

第一次執行 countDown(3) 時，程式沒辦法馬上得到最後的 return，因為它還需要知道 countDown(2) 的結果。

而 countDown(2) 又需要等待 countDown(1)，最後一路呼叫到 countDown(0)：

countDown(3)
↓
countDown(2)
↓
countDown(1)
↓
countDown(0)

這時 Call Stack 可以想成：

┌──────────────┐
│ countDown(0) │ ← 最後進來
├──────────────┤
│ countDown(1) │
├──────────────┤
│ countDown(2) │
├──────────────┤
│ countDown(3) │ ← 最早進來
└──────────────┘

實際看看 Call Stack 怎麼堆疊

只有用文字畫 Stack 還是有點抽象，所以我另外使用 Loupe (Loupe－JavaScript 執行流程視覺化工具) 實際觀察函式執行時 Call Stack 的變化。

Loupe 是一個可以將 JavaScript Call Stack、Web APIs、Callback Queue 等執行狀態視覺化的工具。

實際把 countDown(3) 放進去執行後，可以看到 countDown 不斷呼叫自己時，新的函式呼叫會一層一層進入 Call Stack；直到 countDown(0) 遇到 Base Case，不再繼續呼叫自己，才開始反過來一層一層離開 Stack。

我也把實際操作的過程錄了下來：

從動畫來看就更容易理解：遞迴並不是 countDown(3) 執行完之後才執行 countDown(2)，而是 countDown(3) 還在等待結果時，countDown(2) 就先進入 Call Stack 執行。

這也是為什麼遞迴呼叫會產生一層一層堆疊的現象。

那遞迴為什麼可以「回來」？

當 countDown(0) 遇到 Base Case：

return '倒數結束'

它終於不再呼叫自己，因此開始回傳結果。

接下來就會按照 Stack 後進先出的順序一層一層回去：

countDown(0) 完成
↓
countDown(1) 完成
↓
countDown(2) 完成
↓
countDown(3) 完成

所以我現在才理解，昨天一直說的「遞迴回來」，並不是程式真的跑回前面的程式碼，而是 Call Stack 裡還保留著前面尚未完成的函式呼叫。

等最裡面的函式得到結果後，外層函式才有辦法繼續完成剩下的工作。

那連續呼叫函式也會進 Call Stack 嗎？

我原本還有另一個疑問：

function callHello() {
  console.log('Hello World')
}

callHello()
callHello()
callHello()

這樣算不算 Stack？

答案是算。

每次執行 callHello() 時一樣會進入 Call Stack，只是第一個 callHello() 執行完就離開 Stack，接著才執行第二個。

所以它的過程比較像：

進入 → 完成 → 移除
進入 → 完成 → 移除
進入 → 完成 → 移除

而遞迴不一樣：

進入 → 還沒完成
       ↓
      再進入 → 還沒完成
                ↓
               再進入……

因此真正造成 Stack 疊得很高的原因，不是「同一個函式被呼叫很多次」，而是：

前面的函式還沒執行完，新的函式呼叫就又進來了。

如果一直不回來呢？Stack Overflow

這也讓我終於理解為什麼遞迴一定要有 Base Case。

假設寫成：

function infinity() {
  return infinity()
}

infinity()

函式會一直呼叫自己，每一層都還沒完成，又產生下一層呼叫。

Call Stack 能使用的空間並不是無限的，當呼叫層數持續增加到超過限制，就可能出現 Stack Overflow，例如瀏覽器常見的：

RangeError: Maximum call stack size exceeded

所以昨天學 Base Case 時，只知道它是「讓遞迴停止的條件」；今天學完 Call Stack 才真正理解：

Base Case 不只是停止遞迴，也是讓 Call Stack 終於可以開始一層一層往回清空。

今天的小結

今天把 Call Stack 跟遞迴放在一起看之後，我終於比較理解「遞迴為什麼可以回來」。

函式被呼叫時會進入 Call Stack；如果函式還沒完成又呼叫下一個函式，前一層就會留在 Stack 中等待。

而遞迴正是不斷重複這個過程：

呼叫自己 → 疊上去 → 遇到 Base Case → 開始回傳 → 一層一層移除。

所以我覺得今天最重要的不是記住 Call Stack 這個名詞，而是看懂：

程式現在執行到哪一層？哪些函式還在等待？又會按照什麼順序回來？

這也讓昨天學到的 Recursion，終於從「函式一直呼叫自己」，變成一個比較看得見的執行流程。

參考資料

bun.coding，〈JavaScript 學習筆記 — Call Stack 呼叫堆疊〉
https://medium.com/@bun.coding/javascript%E5%AD%B8%E7%BF%92%E7%AD%86%E8%A8%98-call-stack-%E5%91%BC%E5%8F%AB%E5%A0%86%E7%96%8A-d163c05d1035

PJCHENder，〈JavaScript Event Loop、Stack、Queue〉
https://pjchender.dev/javascript/js-event-loop-stack-queue/

Loupe，JavaScript 執行流程視覺化工具
https://latentflip.com/loupe/