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

尾調(diào)用是函數(shù)式編程里比較重要的一個(gè)概念，尾調(diào)用的概念非常簡(jiǎn)單，一句話就能說(shuō)清楚，它的意思是在函數(shù)的執(zhí)行過(guò)程中，如果最后一個(gè)動(dòng)作是一個(gè)函數(shù)的調(diào)用，即這個(gè)調(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)用，即使語(yǔ)義完全一樣。情況二也屬于調(diào)用后還有操作，即使寫在一行內(nèi)。。

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

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

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

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

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

尾遞歸

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

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

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

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

以 n = 5 來(lái)說(shuō)，fibonacci 函數(shù)的調(diào)用棧會(huì)像這樣展開：

[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 項(xiàng)調(diào)用棧長(zhǎng)度就有 8 了，一些復(fù)雜點(diǎn)的遞歸稍不注意就會(huì)超出限度，同時(shí)也會(huì)消耗大量?jī)?nèi)存。而如果用尾遞歸的方式來(lái)優(yōu)化這個(gè)過(guò)程，就可以避免這個(gè)問(wèn)題，用尾遞歸來(lái)求 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 會(huì)依次遞減 1，它實(shí)際上是用來(lái)記錄遞歸剩余的次數(shù)。而 a 和 b 兩個(gè)參數(shù)在每次遞歸時(shí)也會(huì)在計(jì)算后再次傳入 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 

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

注意

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

由于尾遞歸是尾調(diào)用的一種特殊形式，相對(duì)簡(jiǎn)單一些，在 ES6 沒(méi)有開啟尾調(diào)用優(yōu)化的時(shí)候，我們可以手動(dòng)為尾遞歸做一些優(yōu)化。

尾遞歸優(yōu)化

改寫為循環(huán)

之所以需要優(yōu)化，是因?yàn)檎{(diào)用棧過(guò)多，那么只要避免了函數(shù)內(nèi)部的遞歸調(diào)用就可以解決掉這個(gè)問(wèn)題，其中一個(gè)方法是用循環(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)用棧的無(wú)限增加。

蹦床函數(shù)

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

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

可以看到，這里也沒(méi)有在函數(shù)內(nèi)部調(diào)用函數(shù)，而是在循環(huán)中重復(fù)調(diào)用同一個(gè)函數(shù)，這也避免了增加調(diào)用棧長(zhǎng)度，下面要做的是將原來(lái)的 Fibonacci 函數(shù)改寫為每次返回另一個(gè)函數(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 

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

實(shí)際上，真正的尾遞歸優(yōu)化并非像上面一樣，上面的兩種方法實(shí)際上都改寫了尾遞歸函數(shù)本身，而真正的尾遞歸優(yōu)化應(yīng)該是非入侵式的，下面是尾遞歸優(yōu)化的一種實(shí)現(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
 }
 }
}

然后將原來(lái)的 fibonacciTail 函數(shù)傳入 tailCallOptimize 函數(shù)，得到一個(gè)新函數(shù)，這個(gè)新函數(shù)的執(zhí)行過(guò)程就是經(jīng)過(guò)尾遞歸優(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. 首先通過(guò)閉包，在 tailCallOptimize 的作用域中保存唯一的 active 和 accumulated，其中 active 指示尾遞歸優(yōu)化過(guò)程是否開始，accumulated 用來(lái)存放每次遞歸調(diào)用的參數(shù)，push 方法將參數(shù)入列，shift 方法將參數(shù)出列，保證先進(jìn)先出順序執(zhí)行。

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

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

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

問(wèn)題

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

難以辨別

在引擎層面消除尾遞歸是一個(gè)隱式行為，函數(shù)是不是符合尾調(diào)用的要求，可能程序員在寫代碼的時(shí)候不會(huì)意識(shí)到，另外由于開啟了尾調(diào)用優(yōu)化，一旦出現(xiàn)了死循環(huán)尾遞歸，又不會(huì)引發(fā)溢出，難以辨別。下面介紹一些識(shí)別尾調(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ù)可以使用一個(gè)表達(dá)式作為自己的函數(shù)體，函數(shù)返回值就是這個(gè)表達(dá)式的返回值，在表達(dá)式中，以下幾種情況可能包含尾調(diào)用：

三元運(yùn)算符(? :)

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)用的定義。

邏輯運(yùn)算符（|| 與 &&）

首先是 || 運(yùn)算符：

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

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

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

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

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

將函數(shù)改寫為：

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

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

逗號(hào)運(yùn)算符（,）

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

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

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

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

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

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

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

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

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

function foo() { 
 bar()
}

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

function foo() { 
 bar()
 return undefined
}

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

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

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

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

堆棧信息丟失

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

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

附手動(dòng)優(yōu)化語(yǔ)法

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

總結(jié)

以上就是這篇文章的全部?jī)?nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作能帶來(lái)一定的幫助，如果有疑問(wèn)大家可以留言交流。

最新評(píng)論