多种方式实现斐波那契数列(JS)1

数学上是以递归的方法来定义

F(0) = 0;
F(1) = 1;
F(n) = F(n - 1) + F(n - 2);

1. 公式版：递归 (性能差)

function fib(n) {
  if(n < 0) throw new Error('输入的数字不能小于0');
  if (n < 2) {
    return n;
  }
  return fib(n - 1) + fib(n - 2);
}

正常递归版本是一个既简单又直接的逻辑，但是这个版本有个问题就是存在大量重复计算。如：当 n 为 5 的时候要计算fib(4) + fib(3)当 n 为 4 的要计算fib(3) + fib(2) ，这时fib(3)就是重复计算了。运行 fib(50) 等半天才会出结果。

2. 迭代:for 循环

function fib(n) {
  if(n < 0) throw new Error('输入的数字不能小于0');
  let f0 = 0,
    f1 = 1,
    curFib = f0;
  if (n < 2) {
    return n;
  }
  for (let i = 1; i < n; i++) {
    curFib = f0 + f1;
    f0 = f1;
    f1 = curFib;
  }
  return curFib;
}

这个版本没有重复计算问题，速度也明显快了很多。这并不代表循环比递归好。循环的问题在于状态变量太多，为了实现 fib 这里使用了 4 个状态变量(f0,f1,curFib,i) 而状态变量 在写、修改、删除的过程中需要格外小心。状态变量多了阅读起来也不那么优美了。

3. 去除重复计算的递归版本

function fib(n) {
  if(n < 0) throw new Error('输入的数字不能小于0');
  if (n < 2) return n;
  function _fib(n, a, b) {
    if (n === 0) return a;
    return _fib(n - 1, b, a + b);
  }
  return _fib(n, 0, 1);
}

把前两位数字做成参数巧妙的避免了重复计算，性能也有明显的提升。n 做递减运算，前两位数字做递增（斐波那契数列的递增）,这段代码一个减，一个增。

4. 基于 ES6 Generator 实现

function* fib(n) {
  if(n < 0) throw new Error('输入的数字不能小于0');
  let f0 = 1,
    f1 = 1,
    count = 0;
  while (count < n) {
    yield f0;
    [f0, f1] = [f1, f0 + f1];
    count++;
  }
}
for(let n of fib(8)){
  console.log(n);
}

5. 数组方法

function fib(n) {
  if(n < 0) throw new Error('输入的数字不能小于0');
  if (n < 2) {
    return n;
  }
  let list = [];
  list[0] = 0;
  list[1] = 1;
  for (let i = 1; i < n; i++) {
    list[i + 1] = list[i] + list[i - 1];
  }
  return list[n];
}