快捷導(dǎo)航

js尾調(diào)用優(yōu)化的實(shí)現(xiàn)

更新時(shí)間：2019年05月23日 09:25:01 作者：阮一峰

這篇文章主要介紹了js尾調(diào)用優(yōu)化的實(shí)現(xiàn)，尾調(diào)用（Tail Call）是函數(shù)式編程的一個(gè)重要概念，本文介紹它的含義和用法。感興趣的可以了解一下

尾調(diào)用（Tail Call）是函數(shù)式編程的一個(gè)重要概念，本文介紹它的含義和用法。

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

尾調(diào)用的概念非常簡(jiǎn)單，一句話就能說清楚，就是指某個(gè)函數(shù)的最后一步是調(diào)用另一個(gè)函數(shù)。

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

上面代碼中，函數(shù)f的最后一步是調(diào)用函數(shù)g，這就叫尾調(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)。

尾調(diào)用不一定出現(xiàn)在函數(shù)尾部，只要是最后一步操作即可。

function f(x) {
 if (x > 0) {
  return m(x)
 }
 return n(x);
}

上面代碼中，函數(shù)m和n都屬于尾調(diào)用，因?yàn)樗鼈兌际呛瘮?shù)f的最后一步操作。

二、尾調(diào)用優(yōu)化

尾調(diào)用之所以與其他調(diào)用不同，就在于它的特殊的調(diào)用位置。

我們知道，函數(shù)調(diào)用會(huì)在內(nèi)存形成一個(gè)"調(diào)用記錄"，又稱"調(diào)用幀"（call frame），保存調(diào)用位置和內(nèi)部變量等信息。如果在函數(shù)A的內(nèi)部調(diào)用函數(shù)B，那么在A的調(diào)用記錄上方，還會(huì)形成一個(gè)B的調(diào)用記錄。等到B運(yùn)行結(jié)束，將結(jié)果返回到A，B的調(diào)用記錄才會(huì)消失。如果函數(shù)B內(nèi)部還調(diào)用函數(shù)C，那就還有一個(gè)C的調(diào)用記錄棧，以此類推。所有的調(diào)用記錄，就形成一個(gè)"調(diào)用棧"（call stack）。

尾調(diào)用由于是函數(shù)的最后一步操作，所以不需要保留外層函數(shù)的調(diào)用記錄，因?yàn)檎{(diào)用位置、內(nèi)部變量等信息都不會(huì)再用到了，只要直接用內(nèi)層函數(shù)的調(diào)用記錄，取代外層函數(shù)的調(diào)用記錄就可以了。

function f() {
 let m = 1;
 let n = 2;
 return g(m + n);
}
f();

// 等同于
function f() {
 return g(3);
}
f();

// 等同于
g(3);

上面代碼中，如果函數(shù)g不是尾調(diào)用，函數(shù)f就需要保存內(nèi)部變量m和n的值、g的調(diào)用位置等信息。但由于調(diào)用g之后，函數(shù)f就結(jié)束了，所以執(zhí)行到最后一步，完全可以刪除 f() 的調(diào)用記錄，只保留 g(3) 的調(diào)用記錄。

這就叫做"尾調(diào)用優(yōu)化"（Tail call optimization），即只保留內(nèi)層函數(shù)的調(diào)用記錄。如果所有函數(shù)都是尾調(diào)用，那么完全可以做到每次執(zhí)行時(shí)，調(diào)用記錄只有一項(xiàng)，這將大大節(jié)省內(nèi)存。這就是"尾調(diào)用優(yōu)化"的意義。

三、尾遞歸

函數(shù)調(diào)用自身，稱為遞歸。如果尾調(diào)用自身，就稱為尾遞歸。

遞歸非常耗費(fèi)內(nèi)存，因?yàn)樾枰瑫r(shí)保存成千上百個(gè)調(diào)用記錄，很容易發(fā)生"棧溢出"錯(cuò)誤（stack overflow）。但對(duì)于尾遞歸來說，由于只存在一個(gè)調(diào)用記錄，所以永遠(yuǎn)不會(huì)發(fā)生"棧溢出"錯(cuò)誤。

function factorial(n) {
 if (n === 1) return 1;
 return n * factorial(n - 1);
}

factorial(5) // 120

上面代碼是一個(gè)階乘函數(shù)，計(jì)算n的階乘，最多需要保存n個(gè)調(diào)用記錄，復(fù)雜度 O(n) 。

如果改寫成尾遞歸，只保留一個(gè)調(diào)用記錄，復(fù)雜度 O(1) 。

function factorial(n, total) {
 if (n === 1) return total;
 return factorial(n - 1, n * total);
}

factorial(5, 1) // 120

由此可見，"尾調(diào)用優(yōu)化"對(duì)遞歸操作意義重大，所以一些函數(shù)式編程語(yǔ)言將其寫入了語(yǔ)言規(guī)格。ES6也是如此，第一次明確規(guī)定，所有 ECMAScript 的實(shí)現(xiàn)，都必須部署"尾調(diào)用優(yōu)化"。這就是說，在 ES6 中，只要使用尾遞歸，就不會(huì)發(fā)生棧溢出，相對(duì)節(jié)省內(nèi)存。

四、遞歸函數(shù)的改寫

尾遞歸的實(shí)現(xiàn)，往往需要改寫遞歸函數(shù)，確保最后一步只調(diào)用自身。做到這一點(diǎn)的方法，就是把所有用到的內(nèi)部變量改寫成函數(shù)的參數(shù)。比如上面的例子，階乘函數(shù) factorial 需要用到一個(gè)中間變量 total ，那就把這個(gè)中間變量改寫成函數(shù)的參數(shù)。這樣做的缺點(diǎn)就是不太直觀，第一眼很難看出來，為什么計(jì)算5的階乘，需要傳入兩個(gè)參數(shù)5和1？

兩個(gè)方法可以解決這個(gè)問題。方法一是在尾遞歸函數(shù)之外，再提供一個(gè)正常形式的函數(shù)。

function tailFactorial(n, total) {
 if (n === 1) return total;
 return tailFactorial(n - 1, n * total);
}

function factorial(n) {
 return tailFactorial(n, 1);
}

factorial(5) // 120

上面代碼通過一個(gè)正常形式的階乘函數(shù) factorial ，調(diào)用尾遞歸函數(shù) tailFactorial ，看起來就正常多了。

函數(shù)式編程有一個(gè)概念，叫做柯里化（currying），意思是將多參數(shù)的函數(shù)轉(zhuǎn)換成單參數(shù)的形式。這里也可以使用柯里化。

function currying(fn, n) {
 return function (m) {
  return fn.call(this, m, n);
 };
}

function tailFactorial(n, total) {
 if (n === 1) return total;
 return tailFactorial(n - 1, n * total);
}

const factorial = currying(tailFactorial, 1);

factorial(5) // 120

上面代碼通過柯里化，將尾遞歸函數(shù) tailFactorial 變?yōu)橹唤邮?個(gè)參數(shù)的 factorial 。

第二種方法就簡(jiǎn)單多了，就是采用ES6的函數(shù)默認(rèn)值。

function factorial(n, total = 1) {
 if (n === 1) return total;
 return factorial(n - 1, n * total);
}

factorial(5) // 120

上面代碼中，參數(shù) total 有默認(rèn)值1，所以調(diào)用時(shí)不用提供這個(gè)值。

總結(jié)一下，遞歸本質(zhì)上是一種循環(huán)操作。純粹的函數(shù)式編程語(yǔ)言沒有循環(huán)操作命令，所有的循環(huán)都用遞歸實(shí)現(xiàn)，這就是為什么尾遞歸對(duì)這些語(yǔ)言極其重要。對(duì)于其他支持"尾調(diào)用優(yōu)化"的語(yǔ)言（比如Lua，ES6），只需要知道循環(huán)可以用遞歸代替，而一旦使用遞歸，就最好使用尾遞歸。

（[說明] 本文摘自我寫的《ECMAScript 6入門》）

五、嚴(yán)格模式

ES6的尾調(diào)用優(yōu)化只在嚴(yán)格模式下開啟，正常模式是無效的。

這是因?yàn)樵谡ＤＪ较拢瘮?shù)內(nèi)部有兩個(gè)變量，可以跟蹤函數(shù)的調(diào)用棧。