JavaScript 尾遞歸

■知識(shí)點(diǎn)

    尾遞歸是遞歸的一種優(yōu)化算法，它從最后開始計(jì)算，每遞歸一次就算出相應(yīng)的結(jié)果，即函數(shù)調(diào)用出現(xiàn)在調(diào)用函數(shù)的尾部，因?yàn)槭俏膊?，所以就不用去保存任何局部變量，返回時(shí)調(diào)用函數(shù)可以直接越過調(diào)用用者，返回到調(diào)用者的調(diào)用者。

■實(shí)例設(shè)計(jì)

下面是階乘的一種普通線性遞歸運(yùn)算。

function f( n ){

    return ( n == 1 ) ? l : n * f( n - l );

}

console.log(f (5) ) ;        //120

使用尾遞歸算法后，則可以使用如下方法。

function f ( n, a ){

    return ( n==l ) ? a : f( n - l, a * n );

}

console.log( f (5 , 1) ); //120

當(dāng)n = 5時(shí)，線性遞歸的遞歸過程如下。

f(5) = {5 * f (4) }

     = {5 * {4 * f(3)}}

     = {5 * {4 * {3 * f(2) }}}

     = {5 * {4 * {3 * {2 * f(1) } } } }

     = {5 * {4 * {3 * {2 * 1}}}}

     = {5 * {4 * {3 * 2}}}

     = {5 * {4 * 6}}

     = {5 * 24}

     = 120

而尾遞歸的遞歸過程如下。

f(5) = f(5, 1)

     = f(4, 5)

     = f(3, 20)

     = f(2, 60)

     = f(1, 120)

     = 120

從上面的代碼中很容易看出，普通遞歸比尾遞歸更加消耗資源，每次重復(fù)的過程調(diào)用都使得調(diào)用鏈條不斷加長(zhǎng)，系統(tǒng)不得不使用棧進(jìn)行數(shù)據(jù)保存和恢復(fù)，而尾遞歸就不存在這樣的問題，因?yàn)樗臓顟B(tài)完全由變量n和a保存。

■小結(jié)

    從理論上分析，尾遞歸也是遞歸的一種類型，不過它的算法具有迭代算法的特征。上面的階乘尾遞歸可以改寫為下面的迭代循環(huán)。

var n = 5 

var w = 1;

for ( var i = 1; i <= 5; i ++ ) {

    w = w * i;

}

console.log ( w );

尾遞歸由于直接返回值，不需要保存臨時(shí)變量，所以性能不會(huì)產(chǎn)生線性增加，同時(shí)JavaScript引擎會(huì)將尾遞歸形式優(yōu)化成非遞歸形式。