怒肝 JavaScript 数据结构 — 斐波那契数列
大家好，我是杨成功。
上一篇介绍了递归，以及如何用递归实现数的阶乘。其实递归大家平时都会碰到，只不过有时候写一个递归函数要改好多次才能走通，缺乏那种能直接写好的直觉。其实还是关键思路没有掌握透。
本篇我们继续用递归解决问题，不过实现对象是大名鼎鼎的斐波那契数列。可能很多人听过这个名字，但不知道它是干啥的。
其实斐波那契数列就是一组数值，每个数值按照一定的规则排列递增。这与上一篇介绍的阶乘有相似之处，数值之间的关系可以用某种最小粒度的表达式写出来。
下面我们进入正题，看如何用递归实现斐波那契数列。
斐波那契数列
斐波那契数列是一个由 0、1、1、2、3、5、8、13、21、34 等数组成的序列。
序列前两位固定值是 0, 1，从第三位开始，每个数值都是前两位数相加之和，以此不断累加。
比如数值 3 由 1+2 得到，数值 5 由 2+3 得到。根据这个规则可以推断，在 n 位置的斐波那契数，是 n-2 位置的数值加上 n-1 位置的数值。
理解到这，我们先用循环实现斐波那契数列：
function fibonacci(n) {
if(n === 0) return 0;
if(n <= 2) return 1;
let value = 0;
let n_2 = 1
let n_1 = 1
for(let i = 3; i <= n; i++) {
value = n_2 + n_1
n_2 = n_1
n_1 = value
}
return value
}
上述代码中，n_2 表示 n-2 位置的值，n_1 表示 n-1 位置的值。我们从位置 3 处开始，在循环体中计算 n_2 + n_1 的值，最后赋予 value，并且将 n_2 和 n_1 的值后移一位，以供下一次循环使用。
这样我们通过循环 + 三个变量，实现了斐波那契数列。
试一下使用效果，结果如下：
第 n 位（n 从零开始）表示的值符合预期，说明该函数可用。
递归实现斐波那契数列
上面介绍了循环实现斐波那契数列的方法，我们再看递归如何实现。
上一篇我们说过，在用递归实现某个功能之前，先梳理思路，找到两个东西：
- 最小粒度的表达式
- 终止条件
前面我们推断出，在 n 位置的斐波那契数，是 n-2 位置的数值加上 n-1 位置的数值，所以表达式就是：
f(n) = f(n-2) + f(n-1)
表达式如上，终止条件呢就是 n <= 2 时返回固定值，因为数列前三个值是固定的。
所以最终的递归函数如下：
function fibonacci(n) {
if(n <= 0) return 0;
if(n <= 2) return 1;
return fibonacci(n-2) + fibonacci(n-1)
}
函数简单吧，看测试结果：
依然满足条件，说明该函数可用。我们用图来看一下这个函数的递归流程：
记忆化斐波那契数
上面我们分别用循环和递归实现了斐波那契数列，其实还有第三种方式，就是记忆化。
记忆化的含义就是将前面计算的值缓存下来，根据这些已有值计算出新值。新值再缓存下来，当后面需要这些一层层缓存下来的值时，可以直接拿来使用。
那为什么要使用记忆化呢？再看上面那张递归流程图。
仔细看，你会发现图中 fibonacci(2) 调用了 3 次，fibonacci(3) 调用了 2 次，这样重复执行函数肯定会降低性能。因此我们可以通过缓存值，也就是记忆化来优化逻辑。
直接上使用记忆化的 fibonacci 函数：
function fibonacciMemoization(n) {
const memo = [0, 1];
const fibonacci = (n) => {
if (memo[n] != null) return memo[n];
return memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
};
return fibonacci(n)
}
这个函数使用我们非常熟悉的闭包，将计算过的值缓存在了 memo 这个数组中。这样的话只要计算过的值都会被复用，减少了多余的函数调用。
我们测试下这个函数：
结果也是没问题的，但要比纯递归性能好了许多。
总结
本篇介绍了非常著名的斐波那契数列，然后我们用循环和递归实现了这个数列。相信看到这里，你对递归和斐波那契数列有一个更明了的认识了。
下一篇，我们就要进入复杂数据结构 —— 树 的学习，加油吧！
本文来源公众号：程序员成功。这是学习 JavaScript 数据结构与算法的第 21 篇，本系列会连续更新一个月。