从斐波那契数列看两种常用算法和优化

欢迎关注我：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和0fib(1) = 1; fib(0) = 0;

通过上面的递归过程，fib(3) 最终转换为fib(1) + fib(0) + fib(1)的求解。

递归的效率并不是最优的，也可能导致栈溢出的问题。

下面是 leetcode 执行用时和内存消耗：

时间复杂度：O(2^N)。

空间复杂度：O(N)。

作者：LeetCode
链接：https://leetcode-cn.com/problems/fibonacci-number/solution/fei-bo-na-qi-shu-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联络作者取得受权，非商业转载请注明出处。

函数尾调用优化

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 执行结果：

时间复杂度：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 执行结果：

时间复杂度：O(N)。

空间复杂度：O(1)

参考

递归算法详解