斐波那契数列问题再思考
斐波那契数列函数是最基本最常见的一个递归函数。它的公式可以表达为f(n) = f(n-1) + f(n-2)，读到这里的时候你也许会想“这个东西都玩烂了有什么可讲的呢”，请不要嫌弃这个简单的问题一定要读下去，其实在编程实现中有一些问题容易会被忽视掉，今天我们来分析分析斐波那契数列的编程实现可以如何写，有哪些优化方式。
1. 最常见的方法 - 暴力递归
这可能是绝大部分程序员第一个想到的实现方法：
const fib = (n) => {
if (n === 1 || n === 2) return 1;
return fib(n - 1) + fib(n - 2);
};
这个方法很简单易懂，如果n是1或者2的时候返回1，其他时候返回其前两值之和。不过这个代码却有一个问题，它的效率是很低的。为何效率低呢？比如我们想要计算f(10)，我们就需要先计算f(9)和f(8)，然后我们计算f(9)，就要先计算f(8)和f(7)，如此类推。我们会发现这是一个递归树的问题，每一个节点都需要计算两个子节点问题，所以我们如果要计算n个节点的时候需要解决的问题个数是指数级的，我们的算法时间复杂度就会是O()。(本算法中没有循环，子问题只有一个加法操作f(n-1) + f(n-2)，时间为O(1))
算法时间复杂度等于子问题个数乘于解决一个子问题需要的时间。
仔细观察我们的算法，其实我们能发现，我们有大量的重复计算。以上面的例子为例，f(8)就在计算f(10)和f(9)的时候就被重复计算了两次，其子问题也会有同样的问题，不断会被重复计算，导致耗费过多。
2. 记录计算过的子问题的解决方法
既然我们知道我们有很多的重复计算，那我们可以把计算过的值存储起来，再次遇见需要它的时候直接调用就好了。我们有n个节点，所以我们可以采用有n空间的数组来实现这个方法。
const fib = (n) => {
if (n < 1) return 0;
let myArray = new Array(n).fill(0);
return helper(myArray, n);
};
const helper = (arr, n) => {
if (n === 1 || n === 2) return 1;
if (arr[n - 1] !== 0) return arr[n - 1];
arr[n - 1] = helper(arr, n - 1) + helper(arr, n - 2);
return arr[n - 1];
}
我们初始化了一个有n个成员的数组，并且每个成员预先赋值0，当我们计算过一个节点的值的时候就把值写进去。当下次我们再遇到这个节点的时候就不需要重复计算了，直接提取其值就可以继续计算了。比如我们计算f(10)的时候就已经计算过f(8)了，所以当我们计算f(9)的时候就可以直接调用其值而不需要重新再计算一遍。
该方法中子问题的个数为O(n)，并没有循环等复杂操作，时间为O(1)，所以其时间复杂度为O(n)。相比较第一个解法，我们已经有了质的提高。
我们已经提到的两个方法都是「自上而下」的(递归方法)，我们其实也可以采用「自下而上」的方法来实现这个问题(迭代方法)。
3. 数组自下而上迭代方法
和上面的方法类似，我们也可以采用一个数组，从前两个元素一路迭代到第n个元素，并返回其值。
const fib = (n) => {
if (n < 1) return 0;
let myArray = [];
myArray[0] = 1;
myArray[1] = 1;
for (let i = 2; i < n; i++) {
myArray[i] = myArray[i - 1] + myArray[i - 2];
}
return myArray[n - 1];
};
这个方法很简单易懂，和上面的方法有共同之处，只是方向是相反的，效率也基本上相同。
4. 进一步优化
其实我们再看看上面的程序，会发现一个小细节。任意一个节点的值其实只关心其前面的两个值，其他的值它是不关心的。我们并不是非要创造一个列表不可，实际上我们只需要两个值来存储其前两个状态即可。也就是说我们可以把空间复杂度能从O(n)减少到O(1)。
const fib = (n) => {
if (n === 1 || n === 2) return 1;
let pre = 1;
let cur = 1;
let sum = 0;
for (let i = 3; i <= n; i++) {
sum = pre + cur;
pre = cur;
cur = sum;
}
return cur;
};
这个优化就叫做「状态压缩」，当我们每次运算的时候只需要用到某数组的一部分的时候就可以考虑进行进一步状态压缩优化了。我们当前这个例子就是把空间的需求从n降到了2。
以上就是关于斐波那契数列代码实现和优化的内容。希望对你有所帮助有所启发。