JS程式設計建議——30：使用遞歸模式

建議30：使用遞歸模式

複雜算法通常比較容易使用遞歸實作。很多傳統算法正是通過遞歸實作的，如階乘函數。

function factorial(n) {

if(n == 0) {

return 1;

} else {

return n * factorial(n – 1);

}

遞歸函數的問題：錯誤定義或缺少終結條件會導緻函數長時間運作，使浏覽器出現假死現象。此外，遞歸函數還會受到浏覽器調用棧大小的限制。

JavaScript引擎所支援的遞歸數量與JavaScript調用棧大小直接相關。隻有IE例外，因為它的調用棧與可用系統記憶體相關，而其他浏覽器有固定的調用棧限制。當使用了太多的遞歸，超過最大調用棧尺寸時，浏覽器會彈出錯誤資訊。

調用棧溢出錯誤可以用try catch語句捕獲。異常類型因浏覽器而不同：在Firefox中，它是一個InternalError錯誤；在Safari和Chrome 中，它是一個RangeError錯誤；在IE中會抛出一個一般性的Error類型；在Opera中不抛出錯誤，但會終止JavaScript引擎。正确處理這些錯誤的方法如下：

try {

recurse();

} catch (ex){

alert("errorInfo");

當出現調用棧尺寸限制的問題時，第一步應該定位在代碼中的遞歸執行個體上。為此，有兩個遞歸模式可供選擇。

第一種是直接遞歸模式，即一個函數調用自身。當發生錯誤時，這種模式比較容易定位。其一般模式如下：

function recurse(){

第二種是精巧模式，它包含兩個函數：

function first(){

second();

function second(){

first();

在這種遞歸模式中，兩個函數互相調用對方，形成一個無限循環。大多數調用棧錯誤與這兩種模式有關。常見的棧溢出原因是一個不正确的終止條件，是以定位模式錯誤的第一步是驗證終止條件。如果終止條件是正确的，那麼算法包含了太多層遞歸，為了能夠安全地在浏覽器中運作，應改用疊代、制表或混合模式。