背景
斐波那契序列又称黄金分割数列，指的是这样一个数列：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 来解决。
