Call Stack

Call stack 是 JS 引擎追蹤本身在調用多個函數的程式碼中位置的機制，是資料結構的一種(電腦中的資料結構有分成 stack, q, tree, graph 等等)

Call stack 可以幫助我們知道 JS 引擎當前正在運行什麼函式以及從該函數中調用了哪些函式等

Call stack 會後進先出 last-in-first-out(LIFO) ，其機制為：

1. 當執行函式 f1 時， JS 引擎將其添加到 call stack 中，然後開始執行該函式

2. 若該函式內部又調用其他函式 f2 ，則將函式 f2 添加到 call stack 中，然後開始執行該函式

3. 當 f2 執行完畢後， JS 引擎將其從 call stack 中取出，並且從 f1 停止的位置繼續執行

4. 當 f1 執行完畢後， JS 引擎將其從 call stack 中取出

function f1() {
  console.log("開始執行f1。。。");
  f2();
  console.log("結束執行f1。。。");
}

function f2() {
  console.log("開始執行f2。。。");
  console.log("結束執行f2。。。");
}

f1();
//開始執行時，JS引擎就會把function f1放進call stack
//執行結束時，JS引擎就會把function f1拿出call stack

// -> 開始執行f1。。。
// -> 開始執行f2。。。
// -> 結束執行f2。。。
// -> 結束執行f1。。。

**!!**如果 call stack 堆疊過高，高出記憶體 RAM 分配給 call stack 的最大空間，則導致「stack overflow」的問題

stack overflow

// 程式設計中，如果一個function執行自己這個function
// 這種狀況稱為遞迴recursion
function hello(){
  console.log("hello...");
  hello(); // 再執行他自己
}

hello();  // 第一個執行

// -> hello...
// -> hello...
// -> .
// -> .
// -> .
// -> 範圍錯誤RangeError : Maximum call stack size exceeded超出大小

遞迴 Recursion

遞迴關係 recurrence relation 是一種定義數列的方式，數列的每一項目定義為前面項的函數

程式語言中，與遞迴演算法 recursive algorithm 有相似的概念 -> 當一個函式內部，執行自己這個函式，這種情況就是遞迴演算法(因此，遞迴演算法絕對會產生 call stack)

例如：我們可以定義數列 S

1. A base case S(1) = 2

需要定義一個 base case (基準情況)。 Base case 的用途是為了避免遞迴演算法產生在 call stack 上無限疊加的情況

2. S(n) = 2 * S(n − 1) for n ≥ 2

以上面的規則可知，S 會是等比數列 2, 4, 8, 16, 32, …

function s(n) {
  if (n == 1) {
    // -> base case
    return 2;
  }
  return 2 * s(n - 1);
}

console.log(s(10)); // -> 1024

練習

//1 + 2 + 3 + ... + n = ?
function addUpto(n) {
  if (n == 1) {
    // -> base case
    return 1;
  }
  return n + addUpto(n - 1);
}

console.log(addUpto(10)); // -> 55
console.log(addUpto(100)); // -> 5050
console.log(addUpto(1000)); // -> 500500

費波那契數列

費波那契數列是以遞迴的方法來定義：

1. F(0) = 0
2. F(1) = 1
3. F(n) = F(n−1) + F(n−2) for all n ≥ 2

ex: F(10) = F(9) + F(8)
F(9) = F(8) + F(7)

所以，費波那契數列的前幾項列出來會是:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

function fsequence(n) {
  if (n == 0) {
    return 0;
  }

  if (n == 1) {
    return 1;
  }

  return fsequence(n - 1) + fsequence(n - 2);
}

console.log(fsequence(10)); // -> 55
console.log(fsequence(11)); // -> 89

費波那契數列在n不斷變大時，後一項與前一項的比例會逐漸趨於黃金比例

for(let i = 2; i < 15; i++){
  console.log(fsequence(i + 1) / fsequence(i));  // n 越來越大時，數值會越趨近於1.618
}

下一篇文章學習進階的繼承、原型鏈、Prototype Inheritance in Constructors。