JavaScript 尾遞歸

■知識點

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

■實例設計

下面是階乘的一種普通線性遞歸運算。

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

當n = 5時，線性遞歸的遞歸過程如下。

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

從上面的代碼中很容易看出，普通遞歸比尾遞歸更加消耗資源，每次重復的過程調(diào)用都使得調(diào)用鏈條不斷加長，系統(tǒng)不得不使用棧進行數(shù)據(jù)保存和恢復，而尾遞歸就不存在這樣的問題，因為它的狀態(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 );

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