iT邦幫忙

9

Week11 - 讓遞迴的Stack永遠不會爆炸的「尾遞迴」真的有那麼神奇嗎 - 尾遞迴篇 [高智能方程式系列]

本文章同時發佈於:

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

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

  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 === 0n === 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),那就可以採用迭代~


謝謝你的閱讀,歡迎指教與討論~

參考資料


尚未有邦友留言

立即登入留言