如何提升JavaScript的递归效率
Nicholas为您讲解如何提升JavaScript的递归效率!

影响JavaScript性能的另外一个杀手就是递归，在上一节中提到采用 memoization技术可以优化计算数值的递归函数，但memoization不是万能的，不是所有的递归函数都可以用memoization技术优 化，本文介绍了这些情况，并介绍了解决办法，就是将递归转换为迭代，同时需要注意，本文末尾介绍的方案不是最终的方案，还需要和上一节优化循环的方案综合 起来才能达到最佳效果。

【原文】Speed up your JavaScript, Part 3

【作者】Nicholas C. Zakas

【译者】明达

以下是对原文的翻译：

递归是拖慢脚本运行速度的大敌之一。太多的递归会让浏览器变得越来越慢直到死掉或者莫名其妙的突然自动退出，所以我们一定要解决在 JavaScript中出现的这一系列性能问题。在这个系列文章的第二篇中， 我曾经简短的介绍了如何通过memoization技术来替代函数中太多的递归调用。memoization是一种可以缓存之前运算结果的技术，这样我们 就不需要重新计算那些已经计算过的结果。对于通过递归来进行计算的函数，memoization简直是太有用了。我现在使用的memoizer是由 Crockford写的，主要应用在那些返回整数的递归运算中。当然并不是所有的递归函数都返回整数，所以我们需要一个更加通用的memoizer()函 数来处理更多类型的递归函数。

// 采用迭代实现的归并排序算法 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]; } 

这 个归并排序算法实现使用了一系列循环来代替递归进行排序。由于归并排序首先要将数组拆分成若干只有一个元素的数组，这个方法更加明确的执行了这个操作，而 不是通过递归函数隐晦的完成。work数组被初始化为包含一堆只有一个元素数组的数组。在循环中每次会合并两个数组，并将合并后的结果放回 work数组中。当函数执行完成后，排序的结果会通过work数组中的第一个元素返回。在这个归并排序的实现中，没有使用任何递归，同样也实现了这个算 法。然而，这样做却引入了大量的循环，循环的次数基于要排序的数组中元素的个数，所以我们可能需要使用在上篇讨论过的技术来进行修订，处理这些额外开销。



总结一下基本原则，不管是什么时候使用递归的时候都应该小心谨慎。memoization和迭代是代替递归的两种解决方案，最直接的结果当然就是避免那个提示脚本失控的对话框。