JavaScript的遞迴與循環效能比較程式碼分析

效能方面，遞迴不比迴圈有優勢。除了多次函數呼叫的開銷，在某些情況下，遞迴還會帶來不必要的重複計算。以計算斐波那契數列的遞歸程式為例。求第n項A(n)時，從第n-2項起，每一項都重複計算。項數越小，重複的次數越多。令B(i)為第i項被計算的次數，則有 

B(i)=1; i=n, n-1 

B(i)=B(i +1)+B(i+2); i
這樣，B(i)形成了一個有趣的逆的斐波那契數列。求A(n)時有： 

B(i)=A(n+1-i) 

換一個角度來看，令C(i)為求A(i)時所需的加法的次數，則有 

C(i)=0; i=0, 1 

C(i)=1+C(i-1)+C(i -1); i>1 

令D(i)=C(i)+1，有 

D(i)=1; i=0, 1 

#D(i)=D(i-1)+D(i-1) 

所以D(i)又形成一個斐波那契數列。並可因此得出： 

C(n)=A(n+1)-1 

而A(n)是以幾何級數增長，這種多餘的重複在n較大時會變得十分驚人。與之相對應的採用循環的程序，有 

B(n)=1; n為任意值 

C(n)=0; n=0, 1 

#C(n)=n-1; n>1 

因而當n較大時，前面所給的採用迴圈的程式會比採用遞迴的程式快很多。 

如循環一樣，遞迴中的這個缺陷也是可以彌補的。我們只需要記住已經計算出來的項，求較高項時，就可以直接讀取先前的項。這種技術在遞歸中很普遍，被稱為「儲存」(memorization)。 

以下是採用儲存技術的求斐波那契數列的遞迴演算法。 

//recursion with memorization 
function fibonacci4(n){ 
var memory = []; //used to store each calculated item 
function calc(n){ 
var result, p, q; 
if (n < 2) { 
memory[n] = n; 
return n; 
} 
else { 
p = memory[n - 1] ? memory[n - 1] : calc(n - 1); 
q = memory[n - 2] ? memory[n - 2] : calc(n - 2); 
result = p + q; 
memory[n] = result; 
return result; 
} 
} 
return calc(n); 
}

以上是JavaScript的遞迴與循環效能比較程式碼分析的詳細內容。更多資訊請關注PHP中文網其他相關文章！