JS编程建议——31：使用迭代

建议31：使用迭代
任何可以用递归实现的算法都可以用迭代实现。迭代算法通常包括几个不同的循环，分别对应算法过程的不同方面。虽然迭代也会导致性能问题，但是使用优化的循环替代长时间运行的递归函数可以提高性能，因为运行一个循环比反复调用一个函数的开销要低。
例如，合并排序算法是最常用的以递归实现的算法。下面是一个简单的合并排序算法：

1. function merge(left, right) {
2. var result = [];
3. while(left.length > 0 && right.length > 0) {
4. if(left[0] < right[0]) {
5. result.push(left.shift());
6. } else {
7. result.push(right.shift());
8. }
9. }
10. return result.concat(left).concat(right);
11. }
12. function mergeSort(items) {
13. if(items.length == 1) {
14. return items;
15. }
16. var middle = Math.floor(items.length / 2), left = items.slice(0, middle), right = items.slice(middle);
17. return merge(mergeSort(left), mergeSort(right));
18. }
    这个合并排序代码相当简单直接，其中mergeSort()函数被调用得非常频繁。对一个超过1500项的数组进行操作，就可能在Firefox 上导致栈溢出。程序陷入栈溢出错误并不一定要修改整个算法，这说明递归不是最好的实现方法。合并排序算法还可以用迭代实现，例如：
19. function mergeSort(items) {
20. if(items.length == 1) {
21. return items;
22. }
23. var work = [];
24. for(var i = 0, len = items.length; i < len; i++) {
25. work.push([items[i]]);
26. }
27. work.push([]);
28. for(var lim = len; lim > 1; lim = (lim + 1) / 2) {
29. for(var j = 0, k = 0; k < lim; j++, k += 2) {
30. work[j] = merge(work[k], work[k + 1]);
31. }
32. work[j] = [];
33. }
34. return work[0];
35. }
    在上面代码中，mergeSort()实现与上一个 merge函数同样的功能却没有使用递归。虽然迭代可能比递归合并排序慢一些，但是它不会像递归那样影响调用栈。将递归算法切换为迭代是避免栈溢出错误的方法之一。