本文章同時發佈於：

• Medium
• iT邦幫忙

大家好，最近因為有一位朋友提到尾遞迴，說這個優化技術「可以讓遞迴跑個一百萬次都沒問題」，驚呆的我，就花了些時間研究他，於是就產生了這個系列。

這個「高智能方程式」系列會以介紹以下為主：

1. 演算法
2. 資料結構
3. 效能優化

而為什麼叫做高智能方程式，主要是因這是我童年很喜歡看的閃電霹靂車的香港名稱，希望各位的code能夠因為這些文章討論而像阿斯拉一樣越跑越快！絕對不是因為這部動畫剛好有程式兩個字的關係(｀∀´)

先說結論

其實他並不是很高深的技術，此優化就是：

將符合尾遞迴形式的遞迴轉換成迭代

什麼是尾遞迴

尾遞迴就是遞迴的事物只能為函數自己

以程式碼來說，如果我們有一個數列[1, 2, 3, 4, 5]，我們要把他們全部相加，以尾遞迴的寫法就是：

function recursive(n, ans = 0) {
    if (n === 0) return ans
    return recursive(n - 1, ans + n) // 回傳的事物只有函數自己
}

如果你是以下的寫法，就不算是尾遞迴：

function recursive(n) {
    if (n === 0) return n
    return n + recursive(n - 1) // 回傳的事物除了函數自己還有n
}

除此之外，如果像這樣recursive(n - 1) + recursive(n - 1)回傳兩個自己也不行，

而當我們「正確的使用尾遞迴」，我們就稱為PTC(Proper Tail Calls)。

以費氏數列來舉例，尾遞迴幫助了我們什麼

大家應該都還是得費氏數列的公式：

間單來說就是：

第一個數字為0，第二個數字為1，除了前兩者，下一個數字都為前兩個數字的和

費氏數列的前六個數為[0, 1, 1, 2, 3, 5]（第零個也是一個數），
我們現在要算出第六個數為多少，在程式上面非常直觀的實作就是：

function fibonacci(n) {
  if (n === 0) return 0;
  if (n === 1) return 1;
  return fibonacci(n - 1) + fibonacci(n - 2)
}
console.log(fibonacci(5))
// 得到5

而在執行的時候我們的Stack(記憶體)，到底發生了什麼事呢？我們可以在程式碼裡面加入debugger：

function fibonacci(n) {
  debugger
  if (n === 0) return 0;
  if (n === 1) return 1;
  return fibonacci(n - 1) + fibonacci(n - 2)
}
console.log(fibonacci(5))
// 得到5

在Chrome瀏覽器上執行後，Javascript就會停在debugger的地方，

這時候我們可以點選左方的箭頭讓Javascript繼續遞迴，這時你會看到右下角Call Stack的視窗產生了很多個fibonacci，那是因為：

在遞迴未完成時，任何因遞迴函數產生的Stack都不會被釋放掉

所以整體執行會像下圖：

當每次遞迴時，都會再產生新的函數，而新的函數又會再產生新的函數，直到n === 0或n === 1的時候才不會產生新的函數，而是回傳數值，當函數回傳數值的時候，此函數才結束所有的任務，而釋放Stack。

這樣的做法會有兩種問題：

1. Stack因為遞迴佔著空間而消耗太大
2. 許多的重複的函數，例如fibonacci(1)就被呼叫了第五次

所以如果你執行這個遞迴1000000次，就會爆炸：

function fibonacci(n) {
  if (n === 0) return 0;
  if (n === 1) return 1;
  return fibonacci(n - 1) + fibonacci(n - 2)
}
console.log(fibonacci(1000000))

這時候如果我們啟用尾遞迴，他就會正常，我先貼上最後的答案：

function trampolines (fn) {
  return (...args) => {
    let result = fn(...args)
    while (typeof result === 'function') result = result()
    return result
  }
}

function fibonacci(n, ans = [0, 1]) {
  if (n === 0) return ans[0]
  if (n === 1) return ans[1]
  if (n <= 2) return ans[ans.length - 1] + ans[ans.length - 2]
  ans.push(ans[ans.length - 1] + ans[ans.length - 2])
  return () => fibonacci(n - 1, ans);
}
console.log(trampolines(fibonacci)(1000000))
// 雖然會顯示Infinity，但這主要是因為數字太大了Javascript不支援，但是是可以運行的

這倒是怎麼運作的呢？我依序以下來分析：

1. 迭代版
2. 尾遞迴版
3. 配合trampolines來彌補Chrome沒有尾遞迴優化功能的尾遞迴版

首先，先以迭代的方式思考

我們可以通過數列的方式來思考，如果我們要取第六個數，可以列出以下數列

[0, 1, 1, 2, 3, 5]

第零個與第一個數是我們已知的，所以我們可以先預設好，剩下的數字每個值都是前兩個直相加，所以我們可以寫成以下程式碼：

function fibonacci(n) {
  let ans = [0, 1]
  if (n === 0) return ans[0]
  if (n === 1) return ans[1]
  for(let i = 2; i <= n; i++) {
    ans.push(ans[ans.length - 1] + ans[ans.length - 2])
  }
  return ans[ans.length - 1];
}
console.log(fibonacci(5))

可以發現，其實這樣的迭代已經與尾遞迴的寫法相同了，他們關鍵的差異就是：

• 迭代是宣告ans為一個區域變數，然後每次迭代都改變它
• 尾遞迴的寫法是透過參數將ans帶入下一次的遞迴

將迭代改成尾遞迴版

把以上迭代的程式改為遞迴形式，並將ans以參數帶入下次遞迴就會變成如下：

function fibonacci(n, ans = [0, 1]) {
  if (n === 0) return ans[0]
  if (n === 1) return ans[1]
  if (n <= 2) return ans[ans.length - 1] + ans[ans.length - 2]
  ans.push(ans[ans.length - 1] + ans[ans.length - 2])
  return fibonacci(n - 1, ans);
}
console.log(fibonacci(5))

而這時候，因為改為了PTC的形式，在以往個Chrome就會啟用TCO(Tail Call Optimization)優化機制來釋放Stack，會用「正規的尾遞迴優化」，

但是現在Chrome不會啟用TCO機制了

為什麼呢？至於原因稍後會說明。

使用trampolines達到TCO的尾遞迴版

既然現在Chrome沒有TCO優化機制，要如何釋放掉Stack，必須我們自己來實作，這時候我們會採用一個叫做trampolines的一個函數，他的作用就是：

將遞迴轉換成迭代

為了配合trampolines，我們需要將尾遞迴做一點手腳，改為閉包，

為什麼要這樣呢？我們一行一行分析：

function trampolines (fn) { // 讀取一開始的函數
  return (...args) => { // 將函數的參數讀取
    let result = fn(...args) // 第一次執行函數，如果獲得閉包函數，即進入while迴圈
    while (typeof result === 'function') result = result() // 當每次執行函數時，ans的值都透過閉包保存，而因為已經回傳了閉包，所以函數執行完畢，即釋放Stack
    return result // 迭代result至不再回傳閉包函數而是數值時，回傳數值
  }
}

function fibonacci(n, ans = [0, 1]) {
  if (n === 0) return ans[0]
  if (n === 1) return ans[1]
  if (n <= 2) return ans[ans.length - 1] + ans[ans.length - 2]
  ans.push(ans[ans.length - 1] + ans[ans.length - 2])
  return () => fibonacci(n - 1, ans) // 如果回傳不改為閉包，在let result = fn(...args)時就會一次執行完
}
console.log(trampolines(fibonacci)(5))

使用閉包可以讓遞迴不一次執行完，並透過trampolines來執行且釋放Stack，其關鍵如下：

• 一次執行完會導致：「每次回傳都是再呼叫一個函數」，所以在「最後回傳數值」前都沒有任何一個函數執行完畢，而Stack也就沒辦法釋放。
• 回傳閉包會導致：「每次回傳都是一個閉包」，所以「每次都讓函數執行完畢」，而Stack就會跟著被釋放，不用等到「最後開始回傳值」才被釋放。

Chrome原本不需要trampolines的幫忙

前面有提到Chrome一開始是支援的自動TCO的，所以我們在寫以下函數寫成PTC時：

function fibonacci(n, ans = [0, 1]) {
  if (n === 0) return ans[0]
  if (n === 1) return ans[1]
  if (n <= 2) return ans[ans.length - 1] + ans[ans.length - 2]
  ans.push(ans[ans.length - 1] + ans[ans.length - 2])
  return fibonacci(n - 1, ans)
}
console.log(fibonacci(5))

就會直接有trampolines配合閉包的效果，那為什麼Chrome後來拿掉了呢？

大家可以看看Chrome引擎V8的討論串，討論串主要是認為，大多數的Javascript開發者，可能對「尾遞迴」不了解，甚至不知道有這個東西，如果TCO機制只要發現PTC時就直接啟動，那大多數人遇到的問題將會是：

偵錯時沒辦法依照Stack慢慢去看遞迴哪邊出問題了，因為Stack早就被釋放了，可是大多數開發者不知道有這機制

你可能會說：那如果開發者可以「明確的說我要尾遞迴」再啟動TCO不就好了嘛？

是的，所以TC39有加入了STC(Syntactic Tail Calls)的proposal，只要在遞迴時加入continue，就是明確的跟引擎說：「請幫我啟動TCO來優化尾遞迴」，範例如下：

function factorial(n, acc = 1) {
  if (n === 1) {
    return acc;
  }

  return continue factorial(n - 1, acc * n)
}

但...此proposal後來沒有被導入，然後，就沒有然後惹(ﾉД`)

如果想要體驗「正規的尾遞迴優化」，目前唯一有支援TCO功能的只有Safari，在啟動嚴謹模式(strict mode)會自動執行TCO，程式碼如下：

'use strict';
function fibonacci(n, ans = [0, 1]) {
  if (n === 0) return ans[0]
  if (n === 1) return ans[1]
  if (n <= 2) return ans[ans.length - 1] + ans[ans.length - 2]
  ans.push(ans[ans.length - 1] + ans[ans.length - 2])
  return fibonacci(n - 1, ans)
}
console.log(fibonacci(1000000))
// 雖然會顯示Infinity，但這主要是因為數字太大了Javascript不支援，但是是可以運行的

最後，我們需要尾遞迴嗎？

事實上，以「達到目標」來說，我們用尾遞迴達到的效果，都可以透過迭代達到，因為尾遞迴本質就是把遞迴轉為迭代，所以當你有天發現你在撰寫的遞迴，可以使用尾遞迴時，那其實就是告訴你目前的函數可以轉為迭代。

所以要選擇尾遞迴還是用迭代呢？我認為這與你目前撰寫的區塊風格有關，

如果你現在這個區塊的風格多是FP的宣告式風格(Declarative)，那可以採用尾遞迴，
如果多是指令式風格(Imperative)，那就可以採用迭代～

謝謝你的閱讀，歡迎指教與討論～

參考資料

• Trampolines in JavaScript
• Good Morning, Functional JS (Day 28, Trampolines) - iT 邦幫忙::一起幫忙解決難題，拯救 IT 人的一天
• Recursion optimization in JS - where is it? PTC, TCO and FUD - DEV Community ?‍??‍?
• Fibonacci sequence in Javascript
• 什么是尾递归？