提升JS性能：将递归转换为迭代

同样的，执行fibonacci(40)这个函数，只会对原有的函数调用40次，而不是夸张的331,160,280次。memoization对于那些有着严格定义的结果集的递归算法来说，简直是棒极了。然而，确实还有很多递归算法不适合使用memoization方法来进行优化。

我在学校时的一位教授一直坚持认为，任何使用递归的情况，如果有需要，都可以使用迭代来代替。实际上，递归和迭代经常会被作为互相弥补的方法，尤其是在另外一种出问题的情况下。将递归算法转换为迭代算法的技术，也是和开发语言无关的。这对JavaScript来说是很重要的，因为很多东西在执行环境中是受到限制的（the importance in JavaScript is greater, though, because the resources of the execution environment are so restrictive.）。让我们回顾一个典型的递归算法，比如说归并排序，在JavaScript中实现这个算法需要下面的代码：

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);
}

//采用递归实现的归并排序算法
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()函数处理一个数组，就可以返回经过排序的数组。注意每次调用mergeSort()函数，都会有两次递归调用。这个算法不可以使用memoization来进行优化，因为每个结果都只计算并使用一次，就算缓冲了结果也没有什么用。如果你使用mergeSort()函数来处理一个包含100个元素的数组，总共会有199次调用。1000个元素的数组将会执行1999次调用。在这种情况下，我们的解决方案是将递归算法转换为迭代算法，也就是说要引入一些循环（关于算法，可以参考这篇《List Processing: Sort Again, Naturally》）：

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

凌众科技专业提供服务器租用、服务器托管、企业邮局、虚拟主机等服务，公司网站：http://www.lingzhong.cn 为了给广大客户了解更多的技术信息，本技术文章收集来源于网络,凌众科技尊重文章作者的版权，如果有涉及你的版权有必要删除你的文章，请和我们联系。以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息，谢谢!