使用递归解决斐波那契数列的性能问题-阿里云开发者社区

开发者社区> 云计算> 正文
登录阅读全文

使用递归解决斐波那契数列的性能问题

简介: 原文:使用递归解决斐波那契数列的性能问题 我们知道斐波那契数列(也称作兔子数列)  1,1,2,3,5,8,13,21,34。。。。。 前两位数固定是1,之后每一位数都是前两位数的之和,这样的数列就是斐波那契数列 那么我们要求这样的数列,就必须要求n-1和n-2位数   func...
原文:使用递归解决斐波那契数列的性能问题

我们知道斐波那契数列(也称作兔子数列)  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次函数,极大的提高了性能

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
云计算
使用钉钉扫一扫加入圈子
+ 订阅

时时分享云计算技术内容,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。

其他文章