Home  >  Article  >  Web Front-end  >  JavaScript recursion and loop performance comparison code analysis

JavaScript recursion and loop performance comparison code analysis

伊谢尔伦
伊谢尔伦Original
2017-07-26 17:40:172086browse

In terms of performance, recursion has no advantage over loops. In addition to the overhead of multiple function calls, recursion can also lead to unnecessary repeated calculations in some cases. Take, for example, a recursive program that calculates the Fibonacci sequence. When finding the nth item A(n), starting from the n-2nd item, each item is calculated repeatedly. The smaller the number of items, the more times it is repeated. Let B(i) be the number of times the i-th item is calculated, then

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

B(i)=B(i +1)+B(i+2); if3f5dbff00b5486c51d9bc9891c9ab5f1

Let D(i)=C(i)+1, we have

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

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

So D(i) forms another Fibonacci sequence. And it can be concluded:

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

And A(n) grows in a geometric progression, this redundant repetition in n It becomes quite astonishing when larger. The corresponding program using loops has

B(n)=1; n is any value

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

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

Therefore, when n is large, the program using loops given above will be much faster than the program using recursion.

Like loops, this flaw in recursion can also be made up for. We only need to remember the terms that have been calculated, and when finding higher terms, we can directly read the previous terms. This technique is common in recursion and is called memorization.

The following is a recursive algorithm for finding the Fibonacci sequence using storage technology.

//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); 
}

The above is the detailed content of JavaScript recursion and loop performance comparison code analysis. For more information, please follow other related articles on the PHP Chinese website!

Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn