如何使用Javascript优雅地实现斐波那契数列

背景

斐波那契序列又称黄金分割数列，指的是这样一个数列：0、1、1、2、3、5、8、13、21、……在数学上，斐波纳契数列以如下被以递归的方法定义：F0=0，F1=1，Fn=F(n-1)+F(n-2)（n>=2，n∈N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用。其是一串其中前两个数字之后的每个数字都是程序数之和的序列。

递归实现

const fibonacci = (n) => {
  if (!/[0-9]+/.test(n)) return "Not A Number";
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
};
console.log(fibonacci(50));

以上函数使⽤递归的⽅式进⾏斐波那契数列，后续值的重复计算导致效率异常低下。当 n 处于 50 左右时程序几近崩溃状态，需要等待很长一段时间才返回结果。

使用递归+记忆实现

既然出现了重复求值的情况，我们就用记忆的方式来实现，看看 n 处于 50 左右时能否快速输出结果。Memorization 是⼀种将函数执⾏结果⽤变量缓存起来的⽅法。当函数进⾏计算之前，先看缓存对象中是否有上次计算结果，如果有，就直接从缓存对象中获取结果；如果没有，就进⾏计算并将结果保存到缓存对象中。而闭包恰恰能帮助我们实现 Javascript 的 Memorization。

// ①
const fibonacci = (() => {
  const cache = [];
  return (n) => {
    if (!/[0-9]+/.test(n)) return "Not A Number";

    if (cache[n] !== undefined) {
      return cache[n];
    }

    return (cache[n] = n <= 1 ? n : fibonacci(n - 1) + fibonacci(n - 2));
  };
})();

// ②
const fibonacci = (() => {
  const cache = {};
  return (n) => {
    if (!/[0-9]+/.test(n)) return "Not A Number";

    if (n <= 1) return n;

    !cache[n - 2] && (cache[n - 2] = fibonacci(n - 2));

    !cache[n - 1] && (cache[n - 1] = fibonacci(n - 1));

    return (cache[n] = cache[n - 1] + cache[n - 2]);
  };
})();

上述采用了两种方式来实现递归+记忆的斐波那契数列，一种方式采用了数组来进行存储计算过的值，一种方式采用了对象来进行存储计算过的值，但是经过比对发现对象的方式比数组的方式更加有效，原因是调⽤ fibonacci(100)，fibonacci 函数会在首次计算的时候设置cache[100] = xxx，此时数组⻓度为 101，⽽前⾯ 100 项会被初始化为 undefined，而这一步的初始化工作是需要一定时间的，并且这个时间会线性地随着 n 的增大而变长。

动态规划实现

const fibonacci = (n) => {
  // 用一个数组来存储斐波那契数字
  let cache = new Array(n + 2);
  // 先储存第1和第2个斐波那契数字
  cache[0] = 0;
  cache[1] = 1;

  for (let i = 2; i <= n; i++) {
    cache[i] = cache[i - 1] + cache[i - 2];
  }
  return cache[n];
};

这里采用数组来进行存储斐波那契数列的值，用于方便后面的计算，避免重复计算带来的时间损耗。

const fibonacci = (n, prev = 1, next = 1) => {
  let sum = 1;
  for (let i = 3; i <= n; i += 1) {
    sum = prev + next;
    prev = next;
    next = sum;
  }
  return sum;
};

这里采用简单的变量来存储斐波那契数列的值，如果不要求完整输出 n 项之前的斐波那契数字，这个方法是最佳的，因为这里的空间复杂度为 O(1)，明显比上面的 O(n)要好。

动态规划对斐波那契数列做的优化主要体现在空间换时间，不重复求解，根据不同的场景选择上面的计算方式。

尾调用优化实现

"use strict";
const fibonacci = (n, n1 = 1, n2 = 1) => {
  if (n < 2) {
    return n2;
  }
  return fibonacci(n - 1, n2, n1 + n2);
};

在 ES6 规范中，尾调用优化可以实现高效的尾递归方案。ES6 的尾调⽤优化只在严格模式下开启，正常模式下是⽆效的。因此在使用时需要检查当前脚本是否处于严格模式下，如果不在严格模式下，那么请慎用此方法，因为加上严格模式可能会对当前脚本产生一定的破坏。如果你想体验尾调用优化的快感，可以尝试一下Elixir，它将给你带来 一直用就一直爽 的真切感受。

通项公式实现

const fib = (n) => {
  const SQRT_FIVE = Math.sqrt(5);
  return Math.round(
    (1 / SQRT_FIVE) *
      (Math.pow(0.5 + SQRT_FIVE / 2, n) - Math.pow(0.5 - SQRT_FIVE / 2, n))
  );
};

const fibonacci = (n) => {
  let sum = 0;
  for (let i = 1; i <= n; i += 1) {
    sum += fib(i);
  }
  return sum;
};

斐波那契数列在数学上是有通项公式的，其中的开平方运算可以使用 Javascript 的 Math.round 来解决。