JavaScript 遞歸運算

■知識點

遞歸必須由兩部分組成。

    遞歸調(diào)用的過程。 

    遞歸終止的條件。

在沒有限制的情況下，遞歸運算會無終止地自身調(diào)用。因此，在遞歸運算中要結(jié)合if語句進行控制，只有在某個條件成立時才允許執(zhí)行遞歸，否則不允許調(diào)用自身。

■實例設(shè)計

遞歸運算的應(yīng)用場景如下。

(1)求解遞歸問題

其主要解決一些數(shù)學(xué)運算，如階乘函數(shù)、冪函數(shù)和斐波那契數(shù)列。 

【示例1】下面的示例使用遞歸運算來設(shè)計階乘函數(shù)。

var f = function ( x ) {

    if ( x < 2 ) return 1;             //遞歸終止的條件

    else return x * f( x - 1 );        //遞歸調(diào)用的過程

}

console.log ( f ( 5 ));                //返回5的階乘值為120

在這個過程中，利用分支結(jié)構(gòu)把遞歸結(jié)束的條件和遞歸運算分開。

(2)解析遞歸型數(shù)據(jù)結(jié)構(gòu)

    很多數(shù)據(jù)結(jié)構(gòu)都具有遞歸特性，如DOM文檔樹、多級目錄結(jié)構(gòu)、多級導(dǎo)航菜單就、家族譜系結(jié)構(gòu)等。對于這類數(shù)據(jù)結(jié)構(gòu)，使用遞歸算法進行遍歷比較合適。

【示例2】下面使用遞歸運算計算指定節(jié)點內(nèi)所包含的全部節(jié)點數(shù)。

function f( n ){                       //統(tǒng)計指定節(jié)點及其所有子節(jié)點的元素個數(shù)

    var 1 = 0 ;                        //初始化計數(shù)變量

    if( n.nodeType == 1 ) 1 ++ ;       //如果是元素節(jié)點，則計數(shù)

    for( var i = 0; i < child.length; i ++ ){  //獲取子節(jié)點

        1 += f( child[i] );            //遍歷所有子節(jié)點

    }

    return 1;                          //返回節(jié)點數(shù)

}

window.onload = function(){

    console.log( f( document.body ) )  //返回2，即body和script兩個節(jié)點

}