共计 2155 个字符，预计需要花费 6 分钟才能阅读完成。
题目形容
写一个函数，输出 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）
