题目描述
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0,F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
如：
fib(2) == 1、fib(5) == 5力扣原题目地址：https://leetcode.cn/problems/...解决方案 方案一 直接递归
递归自己调用自己，不断执行，直到遇到某一条件停止递归
寻找规律
第0项 == 0
第1项 == 1
第2项 == 第1项 + 第0项
第3项 == 第2项 + 第1项
第4项 == 第3项 + 第2项
......
第i项 == 第i-1项 + 第i-2项 // 从第2项开始，即 i >= 2使用递归表示规律
function fib(i) {
if (i == 0) {
return 0
}
if (i == 1) {
return 1
}
if (i >= 2) {
/**
* 这句话可以理解为：fib(i)函数执行的结果值等于return fib(i - 1) + fib(i - 2)
* 即：fib(i) == fib(i - 1) + fib(i - 2)
* 符合上方规律：第i项 == 第i-1项 + 第i-2项 // 从第2项开始，即 i >= 2
*/
return fib(i - 1) + fib(i - 2)
}
}
console.time()
console.log('斐波那契第10项', fib(10));
// 55
console.timeEnd() // default: 0.279052734375 ms我们使用timeEnd()打印出fib(10)第十项大致递归执行时间，发现是279毫秒。这里是有点慢了，原因举例：
比如我们要执行fib(4)找到第四项的值，在寻找规律中我们不难发现，第二项和第一项都重复计算了，浪费性能，所以这种方式可以实现，但是由于重复计算导致性能并不是太好（所以递归写法在力扣中，是不通过的）
接下来，我们看看能不能减少重复计算，思路是：已经计算过的数据，就不计算了，直接复用
方案二 使用对象缓存保留计算结果，方便复用
思路：
先提前定义一个对象，存储第0项和第1项的值，后续在计算的过程中，计算一项的值，就把这个值存储到对象当中去；如果继续计算发现某一项的值已经存到对象当中去了，就直接用，如果没有存到对象当中，就继续存一份，方便后续的使用，以减少重复计算，提升性能
代码：
let obj = {
0: 0, // 第0项的值为0
1: 1 // 第1项的值为1
}function fib(i) {
if (i == 0) {
return obj[0]
}
if (i == 1) {
return obj[1]
}
/**
* 如果i不在obj中，即i不属于obj的key，比如i == 2
* 就直接新增一份：obj[2] = obj[1] + obj[0]
*等式变换：obj[2] = fib(1) + fib(0)
*以此类推：obj[i] = fib(i - 1) + fib(i - 2)
*这个表达式成立的条件是从i >= 2 开始，也就是i不在obj的key中
*所以如果不在的时候，就存一份使其在，那么后续需要再次计算的时候
*就直接复用即可
* */
// 这是从第2项开始的。若没有的，即之前没计算过的，就直接存一份在对象中，方便下次复用
if (!(i in obj)) {
obj[i] = fib(i - 1) + fib(i - 2)
console.log('看看obj对象中存储的数据', obj);
return fib(i - 1) + fib(i - 2)
} else if (i in obj) { // 若是有的，即之前计算过的，就直接取到这个结果，直接用
return obj[i]
}
}console.log('斐波那契', fib(6));
// 8 打印obj对象截图：
文章图片
这里也可以使用数组去做一个缓存数据，存储一份计算过的值，这里不赘述。思路是一样的，大家可以自己试一下方案三 定义变量累加到某一项
思路：
既然斐波那契数列是累加的，那么咱们就不停的加就行了。当求：fib(6)的时候，咱们就从fib(1)开始加... 当然，要定义一个变量作为累加的容器
代码：
function fib(n) {
let firstVal = 0 // 头一项为0
let secondVal = 1 // 第二项为1
let thirdVal = null // 第三项先定义一个null，预留着后续的累加
if (n == 0) {
return firstVal
}
if (n == 1) {
return secondVal
}
if (n >= 2) {
for (let i = 2;
i <= n;
i++) {
thirdVal = secondVal + firstVal // 这一项等于前一项加上前前一项
/** 相当于整体往前进一位 */
firstVal = secondVal // 把前一项的值赋值给前前一项
secondVal = thirdVal // 把这一项的值赋值给前一项
console.log('看看累加的值', thirdVal);
}
return thirdVal
}
}
console.log('斐波那契', fib(10));
// 55打印累加的值：
文章图片
总结 【力扣之斐波那契数列】好记性不如烂笔头，记录一下吧
^_^ ，虽然前面记录着，后面忘记着...解决斐波那契数列的方式有很多种，比如还可以使用通项公式表达式之类的。主要是思路，在我们日常工作中，对于一些数据的校验、以及数据架构加工，常常需要使用一点算法的思想在里面，这样写出来的代码，才优雅（装X）
