遞歸是拖慢腳本運行速度的大敵之一。太多的遞歸會讓瀏覽器變得越來越慢直到死掉或者莫名其妙的突然自動退出，所以我們一定要解決在JavaScript中出現(xiàn)的這一系列性能問題。

我們可以通過memoization技術來替代函數(shù)中太多的遞歸調用。memoization是一種可以緩存之前運算結果的技術，這樣我們就不需要重新計算那些已經(jīng)計算過的結果。

對于通過遞歸來進行計算的函數(shù)，memoization簡直是太有用了。我現(xiàn)在使用的memoizer是由Crockford寫的，主要應用在那些返回整數(shù)的遞歸運算中。當然并不是所有的遞歸函數(shù)都返回整數(shù)，所以我們需要一個更加通用的memoizer()函數(shù)來處理更多類型的遞歸函數(shù)。

function memoizer(fundamental, cache) {   
  cachecache = cache || {};   
  var shell = function(arg) {   
      if (! (arg in cache)) {   
          cache[arg] = fundamental(shell, arg);   
      }   
      return cache[arg];   
  };   
  return shell;   
} 

這個版本的函數(shù)和Crockford寫的版本有一點點不同。首先，參數(shù)的順序被顛倒了，原有函數(shù)被設置為***個參數(shù)，第二個參數(shù)是緩存對象，為可選參數(shù)，因為并不是所有的遞歸函數(shù)都包含初始信息。在函數(shù)內部，我將緩存對象的類型從數(shù)組轉換為對象，這樣這個版本就可以適應那些不是返回整數(shù)的遞歸函數(shù)。在shell函數(shù)里，我使用了in操作符來判斷參數(shù)是否已經(jīng)包含在緩存里。這種寫法比測試類型不是undefined更加安全，因為undefined是一個有效的返回值。我們還是用之前提到的斐波納契數(shù)列來做說明：

var fibonacci = memoizer(function(recur, n) {   
  return recur(n - 1) + recur(n - 2);   
}, { "0": 0, "1": 1} ); 

同樣的，執(zhí)行fibonacci(40)這個函數(shù)，只會對原有的函數(shù)調用40次，而不是夸張的331,160,280次。memoization對于那些有著嚴格定義的結果集的遞歸算法來說，簡直是棒極了。然而，確實還有很多遞歸算法不適合使用memoization方法來進行優(yōu)化。

有的觀點認為，任何使用遞歸的情況，如果有需要，都可以使用迭代來代替。實際上，遞歸和迭代經(jīng)常會被作為互相彌補的方法，尤其是在另外一種 出問題的情況下。將遞歸算法轉換為迭代算法的技術，也是和開發(fā)語言無關的。這對JavaScript來說是很重要的，因為很多東西在執(zhí)行環(huán)境中是受到限制的。讓我們回顧一個典型的遞歸算法，比如說歸并排序，在JavaScript中實現(xiàn)這個算法需要下面的代碼：

function merge(left, right) {   
  var result = [];   
  while (left.length > 0 && right.length > 0) {   
      if (left[0] < right[0]) {   
          result.push(left.shift());   
      } else {   
          result.push(right.shift());   
      }   
  }   
  return result.concat(left).concat(right);   
}  
 
//采用遞歸實現(xiàn)的歸并排序算法   
function mergeSort(items) {   
  if (items.length == 1) {   
      return items;   
  }   
  var middle = Math.floor(items.length / 2),   
  left = items.slice(0, middle),   
  right = items.slice(middle);   
  return merge(mergeSort(left), mergeSort(right));   
} 

調用mergeSort()函數(shù)處理一個數(shù)組，就可以返回經(jīng)過排序的數(shù)組。注意每次調用mergeSort()函數(shù)，都會有兩次遞歸調用。這個算法不可以使用memoization來進行優(yōu)化，因為每個結果都只計算并使用一次，就算緩沖了結果也沒有什么用。如果你使用mergeSort()函數(shù)來處理一個包含100個元素的數(shù)組，總共會有199次調用。1000個元素的數(shù)組將會執(zhí)行1999次調用。在這種情況下，我們的解決方案是將遞歸算法轉換為迭代算法，也就是說要引入一些循環(huán)：

// 采用迭代實現(xiàn)的歸并排序算法   
function mergeSort(items) {   
  if (items.length == 1) {   
      return items;   
  }   
  var work = [];   
  for (var i = 0,   
  len = items.length; i < len; i++) {   
      work.push([items[i]]);   
  }   
  work.push([]); //in case of odd number of items   
  for (var lim = len; lim > 1; lim = (lim + 1) / 2) {   
      for (var j = 0,   
      k = 0; k < lim; j++, k += 2) {   
          work[j] = merge(work[k], work[k + 1]);   
      }   
      work[j] = []; //in case of odd number of items   
  }   
  return work[0];   
} 

這個歸并排序算法實現(xiàn)使用了一系列循環(huán)來代替遞歸進行排序。由于歸并排序首先要將數(shù)組拆分成若干只有一個元素的數(shù)組，這個方法更加明確的執(zhí)行了這個操作，而不是通過遞歸函數(shù)隱晦的完成。work數(shù)組被初始化為包含一堆只有一個元素數(shù)組的數(shù)組。

在循環(huán)中每次會合并兩個數(shù)組，并將合并后的結果放回work數(shù)組中。當函數(shù)執(zhí)行完成后，排序的結果會通過work數(shù)組中的***個元素返回。在這個歸并排序的實現(xiàn)中，沒有使用任何遞歸，同樣也實現(xiàn)了這個算法。

【編輯推薦】

1. JavaScript中的函數(shù)式編程實踐
2. JavaScript函數(shù)的定義及形式參數(shù)
3. 揭開Javascript閉包的真實面目