最近一个好友准备跳槽，昨天一起打球恰好也谈到这了，问他感觉如何？
“还行，有个斐波那契数列的没弄出来”（学渣，数学忘差不多了，估计把定义都给忘了，但他绝对牛人。）
我说我昨天刚刚看了一个网易公开课，里面谈到了这，世上总有这么巧的事。
什么是斐波那契数列？
1,1,2,3,5,8,13,21,34...
被定义成：从第三项开始，每一项的值都等于前两项的和。
那么好了，定义已经知道了。怎么实现呢？
那就看从哪入手理解了。
var flag = 0;
var pre1 = 1;
var pre2 = 1;
function fnCalculate(init,n) {
if(init === 'init'){
flag = 0;
pre1 = 1;
pre2 = 1;
}
flag++;
if (n <= 2) {
console.log(1);
return;
}
var next;
if (flag < n - 1) {
next = pre1 + pre2;
pre1 = pre2;
pre2 = next;
fnCalculate('continue',n);
} else {
console.log(pre2);
return;
}
}
fnCalculate('init', 8)
这是我的理解，是不是很奇特，有木有？可以打开浏览器开发工具直接复制代码运行查看结果。
这里采用的是计算次数原则。
通过观察数列，我们可以发现前面两项不用计算可以直接返回结果1，从第三项开始：
第三项，需要计算1次加法；
第四项，需要计算2次加法；
第五项，需要计算3次加法；
...依次类推
那么我们可以发现，计算次数=N-2（其中N为斐波那契数列的第N项）
这么做有个好处，减少计算量，因为每次的计算结果都被缓存下来了。
而传统的递归的做法是什么呢？
function fnCalculate(n){
if(n <=2){
return1;
}else{
return fnCalculate(n-1) + fnCalculate(n-2);
}
}
重复计算的次数会成指数级上升。亲测，N=50，花了好几分钟，浏览器卡死。（不信？你试试，别怪我没提醒）
计算次数为(50-2)+(40-2)+(48-2)+...
而前面的计算次数为50-2
而之所以很多人尝试使用这样的方法，估计也是受斐波那契数列定义的影响：
F0=0，F1=1，Fn=F(n-1)+F(n-2)（n>=2，n∈N*）
多思考一点有多么重要。
总结
根据递归算法编写的代码虽然简洁，但每递归一次就产生一次函数调用，在需要优先考虑性能的场景下，应该把递归算法转换成循环算法，以减少函数的调用次数，从而达到优化性能的目的。
网友评论