JavaScript中尾調用Tail Call的示例分析

這篇文章將為大家詳細講解有關JavaScript中尾調用Tail Call的示例分析，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。

什么是尾調用？

尾調用是函數式編程里比較重要的一個概念，尾調用的概念非常簡單，一句話就能說清楚，它的意思是在函數的執行過程中，如果最后一個動作是一個函數的調用，即這個調用的返回值被當前函數直接返回，則稱為尾調用，如下所示：

function f(x) { 
 return g(x)
}

在 f 函數中，最后一步操作是調用 g 函數，并且調用 g 函數的返回值被 f 函數直接返回，這就是尾調用。

而下面兩種情況就不是尾調用：

// 情況一
function f(x){
 let y = g(x);
 return y;
}

// 情況二
function f(x){
 return g(x) + 1;
}

上面代碼中，情況一是調用函數g之后，還有別的操作，所以不屬于尾調用，即使語義完全一樣。情況二也屬于調用后還有操作，即使寫在一行內。。

為什么說尾調用重要呢，原因是它不會在調用棧上增加新的堆棧幀，而是直接更新調用棧，調用棧所占空間始終是常量，節省了內存，避免了爆棧的可能性。用上面的栗子來說，尾調用的調用棧是這樣的：

[f(x)] => [g(x)]

由于進入下一個函數調用時，前一個函數內部的局部變量（如果有的話）都不需要了，那么調用棧的長度不會增加，可以直接跳入被尾調用的函數。如果是非尾調用的情況下，調用棧會長這樣：

[f(x)] => [1 + g(x)]

可以看到，調用棧的長度增加了一位，原因是 f 函數中的常量 1 必需保持保持在調用棧中，等待 g 函數調用返回后才能被計算回收。如果 g 函數內部還調用了函數 h 的話，就需要等待 h 函數返回，以此類推，調用棧會越來越長。如果這樣解釋還不夠直觀的話，尾調用還有一種特殊情況叫做尾遞歸，它的應用更廣，看起來也更直觀。

尾遞歸

顧名思義，在一個尾調用中，如果函數最后的尾調用位置上是這個函數本身，則被稱為尾遞歸。遞歸很常用，但如果沒寫好的話也會非常消耗內存，導致爆棧。一般解釋遞歸會用階乘或者是斐波那契數列求和作為示例，這里用后者來解釋一下。Fibonacci 數列就不多做解釋了，它是一個長這樣的無限長的數列，從第三項開始，每項都是前兩項的和：

0, 1, 1, 2, 3, 5, 8, 13, 21, ...

如果要計算第 n 項（從第 0 項開始）的值的話，寫成遞歸是常用的手段。如果是非尾遞歸的形式，可以寫成這樣：

function fibonacci(n) { 
 if (n === 0) return 0
 if (n === 1) return 1
 return fibonacci(n - 1) + fibonacci(n - 2)
}

以 n = 5 來說，fibonacci 函數的調用棧會像這樣展開：

[fibonacci(5)]
[fibonacci(4) + fibonacci(3)]
[(fibonacci(3) + fibonacci(2)) + (fibonacci(2) + fibonacci(1))]
[((fibonacci(2) + fibonacci(1)) + (fibonacci(1) + fibonacci(0))) + ((fibonacci(1) + fibonacci(0)) + fibonacci(1))]
[fibonacci(1) + fibonacci(0) + fibonacci(1) + fibonacci(1) + fibonacci(0) + fibonacci(1) + fibonacci(0) + fibonacci(1)]
[1 + 0 + 1 + 1 + 0 + 1 + 0 + 1]
5

才到第 5 項調用棧長度就有 8 了，一些復雜點的遞歸稍不注意就會超出限度，同時也會消耗大量內存。而如果用尾遞歸的方式來優化這個過程，就可以避免這個問題，用尾遞歸來求 Fibonacci 數列的值可以寫成這樣：

function fibonacciTail(n, a = 0, b = 1) { 
 if (n === 0) return a
 return fibonacciTail(n - 1, b, a + b)
}

在這里，每次調用后遞歸傳入 fibonacciTail 函數的 n 會依次遞減 1，它實際上是用來記錄遞歸剩余的次數。而 a 和 b 兩個參數在每次遞歸時也會在計算后再次傳入 fibonacciTail 函數，寫成調用棧的形式就很清楚了：

fibonacciTail(5) === fibonacciTail(5, 0, 1) 
fibonacciTail(4, 1, 1) 
fibonacciTail(3, 1, 2) 
fibonacciTail(2, 2, 3) 
fibonacciTail(1, 3, 5) 
fibonacciTail(0, 5, 8) => return 5

可以看到，每次遞歸都不會增加調用棧的長度，只是更新當前的堆棧幀而已。也就避免了內存的浪費和爆棧的危險。

注意

很多介紹尾調用和尾遞歸的文章講到這里就結束了，實際上情況并非這么簡單，尾調用在沒有進行任何優化的時候和其他的遞歸方式一樣，該產生的調用棧一樣會產生，一樣會有爆棧的危險。而尾遞歸之所以可以優化，是因為每次遞歸調用的時候，當前作用域中的局部變量都沒有用了，不需要層層增加調用棧再在最后層層回收，當前的調用幀可以直接丟棄了，這才是尾調用可以優化的原因。

由于尾遞歸是尾調用的一種特殊形式，相對簡單一些，在 ES6 沒有開啟尾調用優化的時候，我們可以手動為尾遞歸做一些優化。

尾遞歸優化

改寫為循環

之所以需要優化，是因為調用棧過多，那么只要避免了函數內部的遞歸調用就可以解決掉這個問題，其中一個方法是用循環代替遞歸。還是以 Fibonacci 數列舉例：

function fibonacciLoop(n, a = 0, b = 1) { 
 while (n--) {
 [a, b] = [b, a + b]
 }
 return a
}

這樣，不存在函數的多次調用，將遞歸轉變為循環，避免了調用棧的無限增加。

蹦床函數

另一個優化方法是借助一個蹦床函數的幫助，它的原理是接受一個函數作為參數，在蹦床函數內部執行函數，如果函數的返回是也是一個函數，就繼續執行。

function trampoline(f) { 
 while (f && f instanceof Function) {
 f = f()
 }
 return f
}

可以看到，這里也沒有在函數內部調用函數，而是在循環中重復調用同一個函數，這也避免了增加調用棧長度，下面要做的是將原來的 Fibonacci 函數改寫為每次返回另一個函數的版本：

function fibonacciFunc(n, a = 0, b = 1) { 
 if (n > 0) {
 [a, b] = [b, a + b]
 return fibonacciFunc.bind(null, n - 1, a, b)
 } else {
 return a
 }
}

trampoline(fibonacciFunc(5)) // return 5

實際的尾遞歸優化

實際上，真正的尾遞歸優化并非像上面一樣，上面的兩種方法實際上都改寫了尾遞歸函數本身，而真正的尾遞歸優化應該是非入侵式的，下面是尾遞歸優化的一種實現：

function tailCallOptimize(f) { 
 let value,
 active = false
 const accumulated = []
 return function accumulator() {
 accumulated.push(arguments)
 if (!active) {
 active = true
 while (accumulated.length) {
 value = f.apply(this, accumulated.shift())
 }
 active = false
 return value
 }
 }
}

然后將原來的 fibonacciTail 函數傳入 tailCallOptimize 函數，得到一個新函數，這個新函數的執行過程就是經過尾遞歸優化的了：

const fibonacciTail = tailCallOptimize(function(n, a = 0, b = 1) { 
 if (n === 0) return a
 return fibonacciTail(n - 1, b, a + b)
})
fibonacciTail(5) // return 5

下面解釋一下這種優化方式的原理。

1. 首先通過閉包，在 tailCallOptimize 的作用域中保存唯一的 active 和 accumulated，其中 active 指示尾遞歸優化過程是否開始，accumulated 用來存放每次遞歸調用的參數，push 方法將參數入列，shift 方法將參數出列，保證先進先出順序執行。

2. 經過 tailCallOptimize 包裝后返回的是一個新函數 accumulator，執行 fibonacciTail 時實際執行的是這個函數，第一次執行時，現將 arguments0 推入隊列，active 會被標記為 true，然后進入 while 循環，取出 arguments0。在 while 循環的執行中，會將參數類數組 arguments1 推入 accumulated 隊列，然后直接返回 undefined，不會遞歸調用增加調用棧。

3. 隨后 while 循環會發現 accumulated 中又多了一個 arguments1，然后再將 arguments2 推入隊列。這樣，在 while 循環中對 accumulated 的操作就是放進去一個、拿出來一個、再放進去一個、再拿出來一個，以此類推。

4. 最后一次 while 循環返回的就是尾遞歸的結果了。

問題

實際上，現在的尾遞歸優化在引擎實現層面上還是有問題的。拿 V8 引擎來說，尾遞歸優化雖然已經實現了，但默認是不開啟的，V8 團隊還是更傾向于用顯式的語法來優化。原因是在他們看來，尾調用優化仍然存在一些問題，主要有兩點：

難以辨別

在引擎層面消除尾遞歸是一個隱式行為，函數是不是符合尾調用的要求，可能程序員在寫代碼的時候不會意識到，另外由于開啟了尾調用優化，一旦出現了死循環尾遞歸，又不會引發溢出，難以辨別。下面介紹一些識別尾調用要注意的地方：

首先，調用函數的方式不重要，以下幾種調用方式只要出現在尾調用位置上都可以被優化： + 普通調用：func(...) + 作為方法調用：obj.method(...) + 使用 call 或 apply 調用：func.call(..) 或 func.apply(...)

表達式中的尾調用

ES6 的箭頭函數可以使用一個表達式作為自己的函數體，函數返回值就是這個表達式的返回值，在表達式中，以下幾種情況可能包含尾調用：

三元運算符(? :)

const a = x => x ? f() : g()

在這里，f 和 g 函數都在尾調用位置上。為了便于理解，可以將函數改寫一下：

const a = x => { 
 if (x) {
 return f()
 } else {
 return g()
 }
}

可見 f 和 g 的返回值都是直接被返回的，符合尾調用的定義。

邏輯運算符（|| 與 &&）

首先是 || 運算符：

const a = () => f() || g()

這里 f 函數不在尾遞歸位置上，而 g 函數在尾遞歸位置上，為什么，把函數改寫一下就清楚了：

const a = () => { 
 const result = f()
 if (result) {
 return result
 } else {
 return g()
 }
}

|| 運算符的結果依賴于 f 函數的返回值，而不是直接返回 f 的返回值，直接返回的只有 g 函數的返回值。&& 運算符的情況也同理：

const a = () => f() && g()

將函數改寫為：

const a = () => { 
 const result = f()
 if (!result) {
 return result
 } else {
 return g()
 }
}

說明 f 函數也不在尾遞歸位置上，而 g 函數在尾遞歸位置上。

逗號運算符（,）

const a = () => (f(), g())

將函數改寫一下：

const a = () => { 
 f()
 return g()
}

可見，在尾遞歸位置上的仍然只有一個 g 函數。

語句中的尾調用

在 JS 語句中，以下幾種情況可能包含尾調用： + 代碼塊中（由 {} 分隔的語句） + if 語句的 then 或 else 塊中 + do-while，while，for 循環的循環體中 + switch 語句的執行代碼塊中 + try-catch 語句的 catch 塊中 + try-finally，try-catch-finally 語句的 finally 塊中

此外，return 語句也可以包含尾調用，如果 return 的表達式包含尾調用，return 語句就包含尾調用，這就不用多解釋了。

單獨的函數調用不是尾調用

下面這個函數是否包含尾調用呢：

function foo() { 
 bar()
}

答案是否定的，還是先將函數改寫一下：

function foo() { 
 bar()
 return undefined
}

可以看到 return 語句返回的只是一個 undefined 而并非 bar 函數的返回值，所以這里不存在尾調用。

尾調用只能出現在嚴格模式中

在非嚴格模式中，大多數引擎會在函數上增加下面兩個屬性： + func.arguments 包含調用函數時傳入的參數 + func.caller 返回當前函數的調用者

但一旦進行了尾調用優化，中間調用幀會被丟棄，這兩個屬性也就失去了本來的意義，這也是在嚴格模式中不允許使用這兩個屬性的原因。

堆棧信息丟失

除了開發者難以辨別尾調用以外，另一個原因則是堆棧信息會在優化的過程中丟失，這對于調試是不方便的，另外一些依賴于堆棧錯誤信息來進行用戶信息收集分析的工具可能會失效。針對這個問題，實現一個影子堆棧可以解決堆棧信息缺失的問題，但這中解決方式相當于對堆棧進行了模擬，不能保證始終符合實際虛擬機堆棧的真實狀態。另外，影子堆棧的性能開銷也是非常大的。

基于以上原因，V8 團隊建議使用特殊的語法來指定尾遞歸優化，TC39 標準委員會有一個還沒有結論的提案叫做從語法上指定尾部調行為，這個提案由來自 Mozilla 和微軟的委員提出。提案的具體內容可以看鏈接，主要是提出了三種手動指定尾調用優化的語法。

附手動優化語法

Return Continue

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

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

let factorial = (n, acc = 1) => continue 
 n == 1 ? acc
 : factorial(n - 1, acc * n);

// or, if continue is an expression form:
let factorial = (n, acc = 1) => 
 n == 1 ? acc
 : continue factorial(n - 1, acc * n);

Function sigil

// # sigil, though it's already 'claimed' by private state.
#function() { /* all calls in tail position are tail calls */ }

// Note that it's hard to decide how to readably sigil arrow functions.

// This is probably most readable.
() #=> expr
// This is probably most in line with the non-arrow sigil.
#() => expr

// rec sigil similar to async functions
rec function() { /* likewise */ } 
rec () => expr

!-return

function () { !return expr }

// It's a little tricky to do arrow functions in this method.
// Obviously, we cannot push the ! into the expression, and even
// function level sigils are pretty ugly.

// Since ! already has a strong meaning, it's hard to read this as
// a tail recursive function, rather than an expression.
!() => expr

// We could do like we did for # above, but it also reads strangely:
() !=> expr

關于“JavaScript中尾調用Tail Call的示例分析”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，使各位可以學到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。