提升JS性能：将递归转换为迭代
⽹页制作Webjx⽂章简介：，在上⼀节中提到采⽤memoization技术可以优化计算数值的递归函数，但memoization不是万能的，不是所有的递归函数都可以⽤memoization技术优化，本⽂介绍了这些情况，并介绍了解决办法，就是将递归转换为迭代.
影响JavaScript性能的另外⼀个杀⼿就是递归，在上⼀节中提到采⽤memoization技术可以优化计算数值的递归函数，但memoization不是万能的，不是所有的递归函数都可以⽤memoization技术优化，本⽂介绍了这些情况，并介绍了解决办法，就是将递归转换为迭代，同时需要注意，本⽂末尾介绍的⽅案不是最终的⽅案，还需要和上⼀节优化循环的⽅案综合起来才能达到最佳效果。
以下是对原⽂的翻译：
递归是拖慢脚本运⾏速度的⼤敌之⼀。太多的递归会让浏览器变得越来越慢直到死掉或者莫名其妙的突然⾃动退出，所以我们⼀定要解决在JavaScript中出现的这⼀系列性能问题。在这个系列⽂章的第⼆篇中，我曾经简短的介绍了如何通过memoization技术来替代函数中太多的递归调⽤。memoization是⼀种可以缓存之前运算结果的技术，这样我们就不需要重新计算那些已经计算过的结果。对于通过递归来进⾏计算的函数，memoization简直是太有⽤了。我现在使⽤的memoizer是由 Crockford写的，主要应⽤在那些返回整数的递归运算中。当然并不是所有的递归函数都返回整数，所以我们需要⼀个更加通⽤的
memoizer()函数来处理更多类型的递归函数。
function memoizer(fundamental, cache) {
cache = cache || {};
var shell = function(arg) {
if (! (arg in cache)) {
cache[arg] = fundamental(shell, arg);
}
return cache[arg];
};
return shell;}
这个版本的函数和Crockford写的版本有⼀点点不同。⾸先，参数的顺序被颠倒了，原有函数被设置为
第⼀个参数，第⼆个参数是缓存对象，为可选参数，因为并不是所有的递归函数都包含初始信息。在函数内部，我将缓存对象的类型从数组转换为对象，这样这个版本就可以适应那些不是返回整数的递归函数。在shell函数⾥，我使⽤了in操作符来判断参数是否已经包含在缓存⾥。这种写法⽐测试类型不是undefined更加安全，因为undefined是⼀个有效的返回值。我们还是⽤之前提到的斐波纳契数列来做说明：
var fibonacci = memoizer(function(recur, n) {
return recur(n - 1) + recur(n - 2);
}, { "0": 0, "1": 1} );
同样的，执⾏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());
}
}
at(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次调⽤。在这种情况下，我们的解决⽅案是将递归算法转换为迭代算法，也就是说要引⼊⼀些循环（关于算法，可以参考这篇《》）：
// 采⽤迭代实现的归并排序算法
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,
js合并两个数组
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和迭代是代替递归的两种解决⽅案，最直接的结果当然就是避免那个。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。