前言

Call Stack，中文「呼叫堆疊」，是一個很重要的概念。這並不是Web相關技術中特有的，不過為了解釋後續的內容，我決定安插一節說一下Call Stack的概念。

Call Stack

Stack 是一個先進後出(First-In-Last-Out / FILO)的資料結構。就像一本本書疊起來，然後只能一本本從最上面開始拿下來。

Call Stack 就是每次函式呼叫，都會將函數的環境狀態保存進Stack，函數的環境狀態通常叫做「Call Frame」，而儲存Call Frame的Stack，就是Call Stack。

最明顯的例子就是遞歸函式，比如：

function sum(accum, end) {
  if (end === 0)
    return accum;
  return sum(accum + end, end -1);
}

sum(0, 5);

sum()是將 0 到 end 之間的整數累加起來，且end必須是大於等於0的整數。

當呼叫sum(0, 5)的時候，Call Stack便會儲存這筆資訊

| Call Stack |
| ---------- |
|            |
|            |
|            |
|            |
|            |
|            |
| sum(0, 5)  |
+------------+

由於sum(0, 5)回傳的是sum(5, 4)。但sum(5, 4)並不是直接的結果，同樣是一個函式呼叫，所以會在Call Stack多添加一筆Call Frame。

| Call Stack |
| ---------- |
|            |
|            |
|            |
|            |
|            |
| sum(5, 4)  |
| sum(0, 5)  |
+------------+

同樣的會直到sum(15, 0)。

|  Call Stack |
| ----------- |
|             |
|  sum(15, 0) |
|  sum(14, 1) |
|  sum(12, 2) |
|  sum(9, 3)  |
|  sum(5, 4)  |
|  sum(0, 5)  |
+-------------+

但是sum(15, 0)的回傳值就是15，這並不是一個函式呼叫，因此可以直接將sum(15, 0)彈出。這邊先將結果記在Stack Top。

|  Call Stack |
| ----------- |
|             |
|     15      |
|  sum(14, 1) |
|  sum(12, 2) |
|  sum(9, 3)  |
|  sum(5, 4)  |
|  sum(0, 5)  |
+-------------+

然後可以一一將Call Frame彈出，最後可以得知sum(0, 5)的結果就是15

|  Call Stack |
| ----------- |
|             |
|             |
|             |
|             |
|             |
|     15      |
|  sum(0, 5)  |
+-------------+

基本上以上就是Call Stack的概念。也是呼叫函式時基本都會發生的，算是函式呼叫的固定成本。後續部分內容與這個概念有關。

本文同時發表於我的隨筆