在javascript編程中，尾調(diào)用是函數(shù)式編程里比較重要的一個概念，它的意思是在函數(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) {

　　return 1 + g(x)

　　}

　　原因是它的最后一步操作是將 g 函數(shù)調(diào)用的返回值和 1 進(jìn)行加法操作，而不是調(diào)用其他函數(shù)，所以它不是尾調(diào)用。

　　為什么說尾調(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ù)列，從第三項(xiàng)開始，每項(xiàng)都是前兩項(xiàng)的和：

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

　　如果要計算第 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 來說，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 項(xiàng)調(diào)用棧長度就有 8 了，一些復(fù)雜點(diǎn)的遞歸稍不注意就會超出限度，同時也會消耗大量內(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í)際上是用來記錄遞歸剩余的次數(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)存的浪費(fèi)和爆棧的危險。

　　注意很多介紹尾調(diào)用和尾遞歸的文章講到這里就結(jié)束了，實(shí)際上情況并非這么簡單，尾調(diào)用在沒有進(jìn)行任何優(yōu)化的時候和其他的遞歸方式一樣，該產(chǎn)生的調(diào)用棧一樣會產(chǎn)生，一樣會有爆棧的危險。而尾遞歸之所以可以優(yōu)化，是因?yàn)槊看芜f歸調(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)化，是因?yàn)檎{(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

　　實(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

　　}

　　}

　　}

　　然后將原來的 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 時實(shí)際執(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é)果了。

　　問題

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

　　難以辨別

　　在引擎層面消除尾遞歸是一個隱式行為，函數(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)用：

　　三元運(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()

　　}

　　}

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

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

　　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)用，這就不用多解釋了。

　　單獨(dú)的函數(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)行用戶信息收集分析的工具可能會失效。針對這個問題，實(shí)現(xiàn)一個 影子堆棧 可以解決堆棧信息缺失的問題，但這中解決方式相當(dāng)于對堆棧進(jìn)行了模擬，不能保證始終符合實(shí)際虛擬機(jī)堆棧的真實(shí)狀態(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

 

來源：餓了么大前端