函數(shù)調(diào)用自身痕寓,稱為遞歸清酥。
當(dāng)遞歸調(diào)用是整個(gè)函數(shù)體中最后執(zhí)行的語(yǔ)句且它的返回值不屬于表達(dá)式的一部分時(shí)讶踪,這個(gè)遞歸調(diào)用就是尾遞歸购公。
遞歸非常耗費(fèi)內(nèi)存萌京,因?yàn)樾枰瑫r(shí)保存成千上百個(gè)調(diào)用幀,很容易發(fā)生“棧溢出”錯(cuò)誤(stack overflow)宏浩。但對(duì)于尾遞歸來(lái)說(shuō)知残,由于只存在一個(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ù)列耙厚,也能充分說(shuō)明尾遞歸優(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) // 超時(shí)
Fibonacci(500) // 超時(shí)
尾遞歸優(yōu)化過(guò)的 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
由此可見(jiàn)薛躬,“尾調(diào)用優(yōu)化”對(duì)遞歸操作意義重大,所以一些函數(shù)式編程語(yǔ)言將其寫入了語(yǔ)言規(guī)格呆细。ES6 亦是如此型宝,第一次明確規(guī)定,所有 ECMAScript 的實(shí)現(xiàn)絮爷,都必須部署“尾調(diào)用優(yōu)化”趴酣。這就是說(shuō),ES6 中只要使用尾遞歸坑夯,就不會(huì)發(fā)生棧溢出(或者層層遞歸造成的超時(shí))岖寞,相對(duì)節(jié)省內(nèi)存。