JS程式設計建議——31：使用疊代

建議31：使用疊代

任何可以用遞歸實作的算法都可以用疊代實作。疊代算法通常包括幾個不同的循環，分别對應算法過程的不同方面。雖然疊代也會導緻性能問題，但是使用優化的循環替代長時間運作的遞歸函數可以提高性能，因為運作一個循環比反複調用一個函數的開銷要低。

例如，合并排序算法是最常用的以遞歸實作的算法。下面是一個簡單的合并排序算法：

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()函數被調用得非常頻繁。對一個超過1500項的數組進行操作，就可能在Firefox 上導緻棧溢出。程式陷入棧溢出錯誤并不一定要修改整個算法，這說明遞歸不是最好的實作方法。合并排序算法還可以用疊代實作，例如：

var work = [];

for(var i = 0, len = items.length; i < len; i++) {

work.push([items[i]]);

work.push([]);

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] = [];

return work[0];

在上面代碼中，mergeSort()實作與上一個 merge函數同樣的功能卻沒有使用遞歸。雖然疊代可能比遞歸合并排序慢一些，但是它不會像遞歸那樣影響調用棧。将遞歸算法切換為疊代是避免棧溢出錯誤的方法之一。