任何可以用遞歸實現的算法都可以用迭代實現。迭代算法通常包括幾個不同的循環,分別對應算法過程的不同方面。雖然迭代也會導致性能問題,但是使用優化的循環替代長時間運行的遞歸函數可以提高性能,因為運行一個循環比反覆調用一個函數的開銷要低。
例如,合併排序算法是最常用的以遞歸實現的算法。下面是一個簡單的合併排序算法:
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上導致棧溢出。程序陷入棧溢出錯誤並不一定要修改整個算法,這說明遞歸不是最好的實現方法。合併排序算法還可以用迭代實現,例如:
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();
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函數同樣的功能卻沒有使用遞歸。雖然迭代可能比遞歸合併排序慢一些,但是它不會像遞歸那樣影響調用棧。將遞歸算法切換為迭代是避免棧溢出錯誤的方法之一。