斐波那契指的是这样一个数列：1、1、2、3、5、8、13、21、34......在数学上，斐波纳契数列以如下被以递归的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）;随着数列项数的增加，前一项与后一项之比越来越逼近黄金分割的数值0.6180339887..… 

问题来了，怎样用代码实现一个斐波那契数列呢？下面是一些方法的总结；

方法一：递归

一提到斐波那契数列估计很多人和我的第一反应是一样的，那便是递归。用递归的方式实现一下，代码如下：

function fabonacci(n) {
      if (n === 0) { 
        return 0;
      } else if (n === 1) {
        return 1;
      } else {
        return fabonacci(n - 1) + fabonacci(n -2);
      }
    }
    var start = new Date();
    var result = fabonacci(50);
    var end = new Date();
    console.log('迭代', result, end.getTime() - start.getTime());

如上我以n=50为例，测算了一下fn(50)所需要的时间，差点吓死宝宝，255s才出答案，也就是说4分多一点才算出来！！！细分析下原因： 

       = (f(1) + f(0)) + f(1) 

方法二：用一个变量来存储算过的数，解决迭代中的重复计算

var cache = {
      0: 0,
      1: 1
    }
    function fabonacci(n) {
      if (typeof cache[n] === 'number') {
        return cache[n];
      }
      var result = cache[n] = fabonacci(n - 1) + fabonacci(n - 2);
      return result;
     }
    var start = new Date();
    var result = fabonacci(50);
    var end = new Date();
    console.log('方法二', result, end.getTime() - start.getTime());

优雅一点的写法如下： 

var cache = {
      0: 0,
      1: 1
    }
    function fabonacci(n) {
      return typeof cache[n] === 'number' ? cache[n] : cache[n] = fabonacci(n - 1) + fabonacci(n - 2);
    }

其中cache也可以换成数组写法如下： 

var cache = [0, 1];
    function fabonacci(n) {
      return typeof cache[n] === 'number' ? cache[n] : cache[n] = fabonacci(n - 1) + fabonacci(n - 2);
    }

有的同志可能喜欢函数式的写法，写法如下： 

function fabonacci() {
      var cache = {
        0: 0,
        1: 1
      }
      return function fabonacci_(n) {
        return typeof cache[n] === 'number' ? cache[n] : cache[n] = fabonacci_(n - 1) + fabonacci_(n - 2);
      }
    }
 
    var start = new Date();
    var result = fabonacci()(50);
    var end = new Date();
    console.log('方法二4', result, end.getTime() - start.getTime());

 你会惊奇的发现，这个大大缩短了运算时间，只要4ms。时间复杂度为O(n)，空间复杂度为O(n)

方法三：用for循环来实现，时间复杂度为O(n)，空间复杂度为O(1)，用时1ms!

递归是往里探寻，比n小的每个值都要重算一遍，同样比n-1小的每一个值都要重新算一遍。 而for循环有点相反的意思，它是从底层算起，知道到达fn(n)。

function fabonacci(n) {
      var last = 0;
      var laster = 1;
      var current = last;
      for (var i = 1; i <= n; i++) {
        last = laster;
        laster = current;
        current = last + laster;
      }
      return current;
    }
    var start = new Date();
    var result = fabonacci(50);
    var end = new Date();
    console.log('方法三1', result, end.getTime() - start.getTime());

该方法变量处理太多，故做了下面的优化版本，避免多个变量的改变  

function fabonacci(n) {
      function fabonacci_(n, a, b) {
        if (n === 0) {
          return a; //注意这里是a，小编第一次写时，写成了0，依旧停留在迭代的思想
        } else {
          return fabonacci_(n - 1, b, a + b);
        }
      }
      return fabonacci_(n, 0, 1);
    }

本文内容仅供个人学习、研究或参考使用，不构成任何形式的决策建议、专业指导或法律依据。未经授权，禁止任何单位或个人以商业售卖、虚假宣传、侵权传播等非学习研究目的使用本文内容。如需分享或转载，请保留原文来源信息，不得篡改、删减内容或侵犯相关权益。感谢您的理解与支持！

链接: https://fly63.com/article/detial/2300