首页 > web前端 > js教程 > 正文

JavaScript的递归与循环性能对比代码分析

伊谢尔伦
发布: 2017-07-26 17:40:17
原创
2106 人浏览过

性能方面,递归不比循环有优势。除了多次函数调用的开销,在某些情况下,递归还会带来不必要的重复计算。以计算斐波那契数列的递归程序为例。求第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中文网其他相关文章!

相关标签:
来源:php.cn
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板