JavaScript recursion and loop performance comparison code analysis

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); i
In this way, B(i) forms an interesting inverse Fibonacci sequence. When finding A(n), we have:

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

Looking at it from another perspective, let C(i) be used to find A(i) The number of additions required is

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

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

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!