前言

遞迴函式是一個很有趣的東西

也常在一些特殊的資料結構上會使用到

而遞迴最主要的構成因素就是在函式裡面呼叫自己，大概長得像是下面的結構：

function recursion(param) {
  recursion(param);
}

// initial call
recursion(initialParam);

但若像上面的結構，不斷地呼叫自己，沒有終止的機制，就會像無窮迴圈一樣，讓電腦記憶體爆掉

因此，遞迴函式裡面必須有一個刹車的機制

流程控制：繼續走？還是回頭？

在流程控制（control flow）上，可以分成兩條路：

  • 符合終止條件：停止
  • 不符合終止條件：呼叫自己

流程圖大概如下：

graph LR A(Initial call) --> B{Continue?} B -->|No| C(Finish) B -->|Yes| D(Call again) D --> E{Continue?} E -->|No| F(Finish) E -->|Yes| H(Call again) H --> I(Go on...)

夢境

我很喜歡用一個比喻去詮釋遞迴的概念，那就是：全面啟動

電影中的主角柯伯如何進入夢境的？

沒錯，睡著就行了！

而在夢中的他，有兩個選擇：

  1. 醒來，回到現實世界
  2. 再睡著一次，進入「夢中夢」，也就是第二層夢境

但不幸的是，隊員的其中一人在出任務的時候受傷而進入昏迷狀態，柯伯必須去下一層救他

原本計畫順利的話，應該就此打道回府才是

然而面對這樣情況，他也無法執行了

任務達成的條件尚未成立

於是他說：「我們必須前往更深處」

go deeper

他只好再睡著一次，去下一層夢境了

然後他終於找回隊員了

該怎麼回到現實世界呢？

沒錯！就是 kick！

would be a kick

執行環境與堆疊

在理解遞迴的同時，也需要先了解這兩個關鍵字作為基礎知識

一個是執行環境（execution context），另一個則是堆疊（stack）

這裡就直接用英文稱呼，比較直覺一點

在 JavaScript 的世界裡，其實有兩種 execution context：

  • 全域執行環境（Global Execution Context）
  • 函式執行環境（Function Execution Context）

而我們這裡討論的，主要是函式執行環境，而所有函式執行環境的最外面，即是所謂的全域執行環境

context 就是記住當下的時空背景：當下的有哪些變數、其值又是什麼

每一次的函式呼叫，就會創造一個新的 context，以便記憶此次呼叫的環境狀態

創造出來 context 則會存放在稱為 stack 的地方

新的 context 建立了之後，就丟進去這個 stack，

因此，stack 裡的順序就會是：舊的在下，新的在上

下一次要去拿 context 的時候，就會先拿到比較新的 context

簡單範例

大致了解 context 與 stack 的概念之後，我們來看一個簡單的範例：階乘的計算

同時，我們把全面啟動的故事也放在手邊（到底是有多愛全面啟動

階乘的數學定義如下：

$$ n! = n \times (n - 1) \times (n - 2) \times \ldots \times 3 \times 2 \times 1 $$

我們要拿指定的初始值 n 去做階乘計算

function factorial(n) {
  // 終止條件
  if (n === 0) {
    return 1;
  } else {
    return n * factorial(n - 1); // 呼叫自己
  }
}

factorial(4); // result: 24
factorial(2); // result: 2
factorial(0); // result: 1

終止條件是，當 n = 0 時，return 1

因為階乘的定義上：

$$ 0! = 1 $$

假設我們的初始值 n = 3，於是我們執行第一次的呼叫：

factorial(3);

柯伯坐在飛機頭等艙舒適的座椅上睡著了，進入了夢境

第一次的呼叫，建立的一個新的 context，裡面有我們帶進去的 n = 3

所以我們可以這樣表示：

Context { n: 3 }

並且將這個 context 丟進 stack 中儲存，可以這樣表示：

Stack = [
  { n: 3 }
];

然而我們的 n 沒有符合終止條件，於是，進行了第二次的呼叫 factorial

柯伯為了解任務，再次睡著進入了夢中夢

此時，我們帶入 factorial 的參數是 n - 1，所以是 3 - 1 = 2，帶入 2

第二次的呼叫，再次建立一個屬於它的 context：

Context { n: 2 }

於是 stack 變成：

Stack = [
  { n: 2 },
  { n: 3 }
];

我們又回到了函式的第二行，再次判斷終止與否，但仍未滿足條件，於是進行第三次的呼叫：

柯伯達成任務了，不料，隊員昏迷不醒，於是他躍身進入下一層夢境

然後再重複了一次遞迴

OK，這次 n = 0，所以要 return 1 回去，至此，不再遞迴下去

柯伯找回遺失的隊員要打道回府了

return 代表結束這個函式，並回傳值

但別忘了，我們現在在第幾層夢境？

柯伯說：「我是誰？我為什麼在這裡？」

啊，我是指在哪一個 context 裡？

最後那一個對吧，也就是 stack 最上面那個：Context: { n: 0 }

所以當我們 return 之後，回到上一次層是：Context: { n: 1 } 這個 context，而不是現實世界（aka Global 的 context）

柯伯醒來一次，回到上一層夢境

然後我們看到上一層這樣寫：return n * factorial(n - 1)

於是，1 跟上一層的 n 相乘之後，又繼續 return 更上一層，一連串的 return

柯伯一行人，藉由一連串的 kick，一路回到現實世界

整個過程像是這樣：

factorial(3);
  3 * factorial(2);
    2 * factorial(1);
      1 * factorial(0);
        return 1;
      return 1 * 1;
    return 2 * 1;
  return 3 * 2;

於是最後我們得到結果就是：

$$ 3! = 6 $$

我們總共呼叫了 factorial 這個函式四次，稱之為遞迴的深度（depth）

如果我們想知道每一次呼叫時的 depth，可以這樣寫：

function factorial(n, depth) {
  console.log("depth: ", depth); // 現在的遞迴深度
  console.log("context: n =", n); // 當前的 n 值，也就是目前的 context
  if (n === 0) {
    return 1;
  } else {
    return n * factorial(n - 1, depth + 1);
  }
}

factorial(2, 1); // 第一次呼叫，所以深度從 1 開始

這樣就可以看到每一個 context 及對應的 depth 了：

depth: 1
context: n = 2
depth: 2
context: n = 1
depth: 3
context: n = 0

於是柯伯轉動手上的陀螺，以避免迷失自我

而這裡的 console.log 則成為各個 context 裡的指標（電影裡稱之為「圖騰」totem）

spinner

但柯伯的陀螺只能判斷是在夢境（aka Function Execution Context）或是現實（aka Global Execution Context）

還是不太方便呢（重點錯

效能考量

由上述的範例可知，每一次的呼叫，就會創造一個 context 並存到 stack 之中

所以遞迴的深度越深，context 也會越多，電腦需要花更多的記憶體去存放這個龐大的 stack

到達極限的時候，就會造成「堆疊溢位」（stack overflow）

遞迴函式自有它簡潔優雅的優點，但優點是用吃重記憶體這個缺點換來的

就像我們以前會說：「Chrome 瀏覽器的速度好快啊！」但它是吃記憶體的大怪獸啊

基於效能的考量，就會衍生出迭代（Iterate）與遞迴（Recursion）的優缺點比較了

有機會再聊這塊

後記

其實一直想要寫關於遞迴的文章

但又不知道從何寫起

而每當在用遞迴函式的時候，總想到全面啟動這部電影

為了寫這篇，我還重新看了一次電影呢 🙈

參考網路上很多關於遞迴的範例

其他常見的遞迴範例還有，像是費式數列、巴斯卡三角、巢狀資料結構的處理……等

他們都寫得很好，我也把連結列在參考資料

或許我並不是想要寫遞迴，而是全面啟動吧 🙃

參考資料