从斐波那契数列看两种常用算法和优化
欢迎关注我：Github
斐波拉契数列是一个非常经典的数学概念，早在 1202 年就由意大利数学家 Leonardo Fibonacci 提出。它的递推方法定义为：F(1) = 1, F(2) = 1, F(n) = F(n - 1) + F(n - 2)（n ≥ 3，n ∈ N）。本文主要从递归、递推两种算法以及记忆化和函数尾调用优化*两种优化方式来探讨它的解法。
递归算法
const fib = function(N) {
if (N <= 1) return N
return fib(N - 1) + fib(N - 2);
};
递归算法英文为 recursion algorithm，是一种直接或者间接调用自身函数或者方法的算法。递归算法的实质是把问题分解成规模缩小的同类问题的子问题，然后递归调用方法来表示问题的解。
递归算法解决问题的特点：
- 递归就是方法里调用自身。
- 在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。
- 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。
- 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等，所以一般不提倡用递归算法设计程序。
上面的算法的递归出口是 if (N <= 1) return N，表示 fib 的第一个和第二位分别是从0和1开始计算。假设我们使用此算法求解 N 为3时 fib 的值，则递归过程如下：
// fib(3)返回fib(2)和fib(1)相加的结果
fib(3) = fib(2) + fib(1);
// fib(2)返回fib(1)和fib(0)相加的结果
fib(2) = fib(1) + fib(0);
// fib(1)和fib(0)触发递归出口的条件，分别返回1和0
fib(1) = 1; fib(0) = 0;
通过上面的递归过程，fib(3) 最终转换为fib(1) + fib(0) + fib(1)的求解。
递归的效率并不是最优的，也可能导致栈溢出的问题。
下面是 leetcode 执行用时和内存消耗：
| 执行用时 | 内存消耗 |
|---|---|
| 80 ms | 34.7 MB |
时间复杂度：O(2^N)。
空间复杂度：O(N)。
函数尾调用优化
const fib = function(N) {
return calc(N, 0, 1);
};
const calc = function(count, n, m) {
if (count === 0) return n;
return calc(count - 1, m, n + m);
}
尾调用（Tail Call）是函数式编程的一个重要概念，是指一个函数里的最后一个动作是调用函数的情形，而函数尾优化就是通过尾调用来优化函数的栈空间大小。
原理：函数调用时会内存形成一个调用帧（call frame），保存调用位置和内部变量等信息，如果函数本身存在递归调用函数的情况，那么所有的调用记录就会形成一个调用栈（call stack）。复杂的嵌套递归会占用大量的栈空间。当编译器检测到一个函数调用是尾递归的时候，它就覆盖当前的活动记录而不是在栈中去创建一个新的。通过覆盖当前的栈帧而不是在其之上重新添加一个，这样所使用的栈空间就大大缩减了，这使得实际的运行效率会变得更高。
上面的代码都满足“最后一个动作是调用函数”这样一种情形，所以属于尾调用。区别于递归算法，函数尾调用优化将 fib(0) 和 fib(1) 的值作为参数默认值传递给了 calc 方法，并且将递归算法返回 fib 前两项相加的运算放在了函数参数中执行，这样就做到了函数尾调用优化。
下面是 leetcode 执行结果：
| 执行用时 | 内存消耗 |
|---|---|
| 64 ms | 34.3 MB |
时间复杂度：O(2^N)。
空间复杂度：O(1)。
记忆化
const fib = function(N) {
return memo(N);
};
function memo(N, arr = []) {
if (N <= 1) return N;
if (!arr[N]) arr[N] = memo(N - 1) + memo(N - 2);
return arr[N];
}
在递归算法时，存在着重复计算的问题，比如求解 fib(4) 时，会将 fib(2) 重复计算两次。虽然在 N 很小时不会造成特别大的性能损耗，而且可能还优于记忆化（记忆化要开辟新的空间存储已计算过的值），不过在处理大数据时记忆化的优势就显示出来了。
上面代码新增一个 arr 数组来存储计算结果，如果 arr 中已经存储了对应的值，则不再重复计算，直接返回存储的结果。
其实，相对于记忆化，有一个更优的算法来求解斐波拉契数列，那就是递推。
时间复杂度：O(N)。
空间复杂度：O(N)。
递推
const fib = function(N) {
if (N <= 1) return N;
const arr = [];
arr[0] = 0;
arr[1] = 1;
for (let i = 2; i <= N; i++) {
arr[i] = arr[i - 1] + arr[i - 2];
}
return arr[N];
};
递推（The Recursive）是给定一组初始值，然后根据规定运算，并最终得到所需结果。如果说递归是从未知到已知，那么递推就是从已知到未知。
递推更加符合人类的思维习惯，从 fib(0) 和 fib(1) 可以计算出 fib(2) 的值，而知道了 fib(1) 和 fib(2) 的值，又可以计算出 fib(3) 的值。以此类推，可以计算出所有值的结果。相对于递归，递推不会出现重复计算的问题，在运行效率上更优。
下面是 leetcode 执行结果：
| 执行用时 | 内存消耗 |
|---|---|
| 56 ms | 33.5 MB |
时间复杂度：O(N)。
空间复杂度：O(1)
