JavaScript中尾調(diào)用Tail Call的示例分析

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

什么是尾調(diào)用？

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

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

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

而下面兩種情況就不是尾調(diào)用：

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

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

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

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

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

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

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

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

尾遞歸

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

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 函數(shù)的調(diào)用棧會像這樣展開：

[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 項調(diào)用棧長度就有 8 了，一些復(fù)雜點的遞歸稍不注意就會超出限度，同時也會消耗大量內(nèi)存。而如果用尾遞歸的方式來優(yōu)化這個過程，就可以避免這個問題，用尾遞歸來求 Fibonacci 數(shù)列的值可以寫成這樣：

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

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

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

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

注意

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

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

尾遞歸優(yōu)化

改寫為循環(huán)

之所以需要優(yōu)化，是因為調(diào)用棧過多，那么只要避免了函數(shù)內(nèi)部的遞歸調(diào)用就可以解決掉這個問題，其中一個方法是用循環(huán)代替遞歸。還是以 Fibonacci 數(shù)列舉例：

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

這樣，不存在函數(shù)的多次調(diào)用，將遞歸轉(zhuǎn)變?yōu)檠h(huán)，避免了調(diào)用棧的無限增加。

蹦床函數(shù)

另一個優(yōu)化方法是借助一個蹦床函數(shù)的幫助，它的原理是接受一個函數(shù)作為參數(shù)，在蹦床函數(shù)內(nèi)部執(zhí)行函數(shù)，如果函數(shù)的返回是也是一個函數(shù)，就繼續(xù)執(zhí)行。

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

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

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

實際的尾遞歸優(yōu)化

實際上，真正的尾遞歸優(yōu)化并非像上面一樣，上面的兩種方法實際上都改寫了尾遞歸函數(shù)本身，而真正的尾遞歸優(yōu)化應(yīng)該是非入侵式的，下面是尾遞歸優(yōu)化的一種實現(xiàn)：

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 函數(shù)傳入 tailCallOptimize 函數(shù)，得到一個新函數(shù)，這個新函數(shù)的執(zhí)行過程就是經(jīng)過尾遞歸優(yōu)化的了：

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

下面解釋一下這種優(yōu)化方式的原理。

1. 首先通過閉包，在 tailCallOptimize 的作用域中保存唯一的 active 和 accumulated，其中 active 指示尾遞歸優(yōu)化過程是否開始，accumulated 用來存放每次遞歸調(diào)用的參數(shù)，push 方法將參數(shù)入列，shift 方法將參數(shù)出列，保證先進(jìn)先出順序執(zhí)行。

2. 經(jīng)過 tailCallOptimize 包裝后返回的是一個新函數(shù) accumulator，執(zhí)行 fibonacciTail 時實際執(zhí)行的是這個函數(shù)，第一次執(zhí)行時，現(xiàn)將 arguments0 推入隊列，active 會被標(biāo)記為 true，然后進(jìn)入 while 循環(huán)，取出 arguments0。在 while 循環(huán)的執(zhí)行中，會將參數(shù)類數(shù)組 arguments1 推入 accumulated 隊列，然后直接返回 undefined，不會遞歸調(diào)用增加調(diào)用棧。

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

4. 最后一次 while 循環(huán)返回的就是尾遞歸的結(jié)果了。

問題

實際上，現(xiàn)在的尾遞歸優(yōu)化在引擎實現(xiàn)層面上還是有問題的。拿 V8 引擎來說，尾遞歸優(yōu)化雖然已經(jīng)實現(xiàn)了，但默認(rèn)是不開啟的，V8 團(tuán)隊還是更傾向于用顯式的語法來優(yōu)化。原因是在他們看來，尾調(diào)用優(yōu)化仍然存在一些問題，主要有兩點：

難以辨別

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

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

表達(dá)式中的尾調(diào)用

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

三元運算符(? :)

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

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

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

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

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

首先是 || 運算符：

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

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

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

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

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

將函數(shù)改寫為：

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

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

逗號運算符（,）

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

將函數(shù)改寫一下：

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

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

語句中的尾調(diào)用

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

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

單獨的函數(shù)調(diào)用不是尾調(diào)用

下面這個函數(shù)是否包含尾調(diào)用呢：

function foo() { 
 bar()
}

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

function foo() { 
 bar()
 return undefined
}

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

尾調(diào)用只能出現(xiàn)在嚴(yán)格模式中

在非嚴(yán)格模式中，大多數(shù)引擎會在函數(shù)上增加下面兩個屬性： + func.arguments 包含調(diào)用函數(shù)時傳入的參數(shù) + func.caller 返回當(dāng)前函數(shù)的調(diào)用者

但一旦進(jìn)行了尾調(diào)用優(yōu)化，中間調(diào)用幀會被丟棄，這兩個屬性也就失去了本來的意義，這也是在嚴(yán)格模式中不允許使用這兩個屬性的原因。

堆棧信息丟失

除了開發(fā)者難以辨別尾調(diào)用以外，另一個原因則是堆棧信息會在優(yōu)化的過程中丟失，這對于調(diào)試是不方便的，另外一些依賴于堆棧錯誤信息來進(jìn)行用戶信息收集分析的工具可能會失效。針對這個問題，實現(xiàn)一個影子堆?？梢越鉀Q堆棧信息缺失的問題，但這中解決方式相當(dāng)于對堆棧進(jìn)行了模擬，不能保證始終符合實際虛擬機(jī)堆棧的真實狀態(tài)。另外，影子堆棧的性能開銷也是非常大的。

基于以上原因，V8 團(tuán)隊建議使用特殊的語法來指定尾遞歸優(yōu)化，TC39 標(biāo)準(zhǔn)委員會有一個還沒有結(jié)論的提案叫做從語法上指定尾部調(diào)行為，這個提案由來自 Mozilla 和微軟的委員提出。提案的具體內(nèi)容可以看鏈接，主要是提出了三種手動指定尾調(diào)用優(yōu)化的語法。

附手動優(yōu)化語法

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

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