尾調(diào)用優(yōu)化
什么是尾調(diào)用熊咽？
尾調(diào)用（Tail Call）是函數(shù)式編程的一個(gè)重要概念，本身非常簡(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;
}
// 情況三
function f(x){
g(x);
}
上面代碼中颁督，情況一是調(diào)用函數(shù)g之后践啄，還有賦值操作，所以不屬于尾調(diào)用沉御，即使語義完全一樣屿讽。情況二也屬于調(diào)用后還有操作，即使寫在一行內(nèi)吠裆。情況三等同于下面的代碼伐谈。
function f(x){
g(x);
return undefined;
}
尾調(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)用之所以與其他調(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(x)的調(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ù)的內(nèi)部變量阶剑，內(nèi)層函數(shù)的調(diào)用幀才會(huì)取代外層函數(shù)的調(diào)用幀跃巡，否則就無法進(jìn)行“尾調(diào)用優(yōu)化”。
function addOne(a){
var one = 1;
function inner(b){
return b + one;
}
return inner(a);
}
上面的函數(shù)不會(huì)進(jìn)行尾調(diào)用優(yōu)化牧愁，因?yàn)閮?nèi)層函數(shù)inner用到了外層函數(shù)addOne的內(nèi)部變量one素邪。
尾遞歸
函數(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
還有一個(gè)比較著名的例子厕鹃，就是計(jì)算 Fibonacci 數(shù)列兢仰，也能充分說明尾遞歸優(yōu)化的重要性。
非尾遞歸的 Fibonacci 數(shù)列實(shí)現(xiàn)如下熊响。
function Fibonacci (n) {
if ( n <= 1 ) {return 1};
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
Fibonacci(10) // 89
Fibonacci(100) // 堆棧溢出
Fibonacci(500) // 堆棧溢出
尾遞歸優(yōu)化過的 Fibonacci 數(shù)列實(shí)現(xiàn)如下旨别。
function Fibonacci2 (n , ac1 = 1 , ac2 = 1) {
if( n <= 1 ) {return ac2};
return Fibonacci2 (n - 1, ac2, ac1 + ac2);
}
Fibonacci2(100) // 573147844013817200000
Fibonacci2(1000) // 7.0330367711422765e+208
Fibonacci2(10000) // Infinity
由此可見，“尾調(diào)用優(yōu)化”對(duì)遞歸操作意義重大汗茄，所以一些函數(shù)式編程語言將其寫入了語言規(guī)格秸弛。ES6 是如此，第一次明確規(guī)定洪碳，所有 ECMAScript 的實(shí)現(xiàn)递览，都必須部署“尾調(diào)用優(yōu)化”。這就是說瞳腌，ES6 中只要使用尾遞歸绞铃，就不會(huì)發(fā)生棧溢出，相對(duì)節(jié)省內(nèi)存嫂侍。
