js 实现斐波那契数列

[cobish]

什么是斐波那契数列？

斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……

在数学上，斐波纳契数列以如下被以递归的方法定义：F(0)=1，F(1)=1, F(n)=F(n-1)+F(n-2)（n>2，n∈N*）

实现方式

1. 循环实现
2. 递归实现

实现的主要思路为 F(n)=F(n-1)+F(n-2)，即后面一个数是由前面两个数相加得来。

循环实现

function fibonacci (n) {
  if (n <= 1) return 1;
  
  var num1 = 1, num2 = 1;
  
  for (var i = 2; i < n; i++) {
    var temp = num2;
    num2 = num1 + num2;
    num1 = temp;
  }
  
  return num2;
}

递归实现

递归实现起来更加的简洁。

function fibonacci (n) {
  if (n <= 1) return 1;
  
  return fibonacci(n - 1) + fibonacci(n - 2);
}

这个方法算是代码最少也容易理解，但是当 n 较大时很快产生栈溢出，引发原因是“调用帧”过多。

主要是因为执行上下文栈里压入过多的函数，但又没及时弹出，解决方案可以使用尾调用（思路跟循环很像）。

// 尾调用
function fibonacci (n, num1, num2) {
  num1 = num1 || 1;
  num2 = num2 || 1;
  
  if (n <= 1) return num2;
  
  return fibonacci(n - 1, num2, num1 + num2);
}

递归实现的比较

前面用到了两种递归的方式，就用执行上下文栈来比较一下它们吧。

ECStack = [];

第一种递归方法的执行上下文栈的变化为：

ECStack.push(<f> functionContext);
ECStack.push(<f> functionContext);
// ...
ECStack.pop();
ECStack.pop();

第二种递归方法（尾调用）的执行上下文栈的变化为：

ECStack.push(<f> functionContext);
ECStack.pop();
// ...
ECStack.push(<f> functionContext);
ECStack.pop();

可以看到第二种递归方法用完就弹出，所以不会导致栈溢出。

尾递归可以参考：JavaScript专题之递归。

[Hibop]

刚使用下生成器和遍历器， 用来写递归也还不错

  // 利用 Generator 函数和for...of循环，实现斐波那契数列
  function* fibonacci() {
    let index = 0; // ==> action : {index, value} Or [index, value]
    let [prev, curr] = [[0], [1, index++]];
    for (;;) {
      yield curr;
      [prev, curr] = [curr, [prev[0] + curr[0], index++]];
    }
  }

  function getFibonacci(index) {
    for (let [n, i] of fibonacci()) {
      // 可以指定第n项, 也可以指定小于1000的最大斐波拉契数
      if (i >= index) {
        console.log(n, i);
        return n;
        break;
      }
    }
  }

[Hibop]

上面写法有点粗糙复杂， 更简洁点的写法

  function* fibonacci(n) {
    for(let [prev, curr] = [0, 1], index = 0; index <= n; index++) {
      yield curr;
      [prev, curr] = [curr, prev + curr];
    }
  }
// 调用, rest可以得到斐波那契数组
[...fibonacci(n)]