我们知道斐波那契数列（也称作兔子数列） 1,1,2,3,5,8,13,21,34。。。。。
前两位数固定是1，之后每一位数都是前两位数的之和，这样的数列就是斐波那契数列
那么我们要求这样的数列，就必须要求n-1和n-2位数
function getFB(n){ if(n == 1 || n == 2){
// 这里我们先保持前两位数是1 return 1; }else { return getFB(n-1) + getFB(n-2); } } console.log(getFB(10));
求斐波那契数列的第十位 在控制台中打印出来的是 55
那么 第五十位呢？。。。。。。。。。
很好，我的浏览器卡死崩溃了
由此我们可知，这样求斐波那契数列实在是太浪费性能了
既然有问题我们就来解决它
那么 求斐波那契数列的时候是为什么会浪费性能呢？
原因就是浏览器求了太多重复项
var i = 0; //声明一个变量,用来记录调用getFB()方法的次数 function getFB(n){ i++; if(n == 1 || n == 2){ return 1; }else { return getFB(n-1) + getFB(n-2); } } console.log(getFB(20));// 我的浏览器求不出来这么多项 所以换了小一点的数字
console.log(i);
求斐波那契数列的第20位会调用13529次函数
那么求第30位呢？
多达16万次
第40位呢？第50 位呢？。。。。。。。
所以这个样子实在是太浪费性能了
解决问题的思路：我们把已经求过的项用一个变量保存起来，如果下次还需要用到这个项就直接取出来用，而不是再去调用函数
var i = 0;//声明一个变量i,记录调用getFB这个函数的次数. //声明一个对象obj,用来保存已经求过的项. var obj = {}; function getFB(n){ i++; //求n位是多少,就先去obj里面看看,之前求过没有,如果之前求过,就直接取出来使用. if(obj[n] != undefined){ //如果进到了这里,说明当前这个n位已经求过,已经存进obj里面了 return obj[n]; }else { //如果进到这里来了,就说明当前这个n位之前没求过,没求过就求呗. if(n == 1 || n == 2){ obj[n] = 1; return 1; }else { obj[n] = getFB(n-1) + getFB(n-2); return obj[n]; } } } console.log(getFB(60)); console.log(i);
那么我们就来看看结果吧
斐波那契数列的第60位大的吓人，但是我们却也只调用了117次函数，极大的提高了性能