1. 裴波那契数列基础版概念
裴波那契数列是 最前的两位数是1， 之后的每个数都是前两个数之和。
数字实例： 1, 1, 2, 3, 5, 8, 13, 21..., 即 n = n-1 + n- 2.
2. 裴波那契数列的实现
function pp (n) {
// 第1位、第2位都是1
if (n === 1 || n === 2) {
return 1
} else {
return pp(n-1) + pp(n-2)
}
}
console.log(pp(10)) // 55
3. 性能检测
利用计数器，我们检测下函数被递归调用了多少次
let i = 0
function pp (n) {
i ++
// 第1位、第2位都是1
if (n === 1 || n === 2) {
return 1
} else {
return pp(n-1) + pp(n-2)
}
}
let n = 30
console.log(`第${n}位的值是：`, pp(n)) // 第30位的值是： 832040
console.log('函数调用次数是', i) // 函数调用次数是 1664079
通过以上代码测试，在获得越大位数时， 函数递归的调用测试如此的多。所以我们需要对它进行进一步的优化，避免这么大计算开销。
4. 优化原理与实现
通过查看规律我们发现，递归函数的调用数字有很多重复情况，我们用个对象来存储其值。 把次位当做key, 位数的值作为value.
let i = 0
let o = {}
function pp (n) {
i ++
if (o[n]) {
return o[n]
}
// 第1位、第2位都是1
if (n === 1 || n === 2) {
return o[n] = 1
} else {
o[n] = pp(n-1) + pp(n-2)
return o[n]
}
}
let n = 30
console.log(`第${n}位的值是：`, pp(n)) // 第30位的值是： 832040
console.log('函数调用次数是', i) // 函数调用次数是 57
通过以上测试发现，性能提升了很多由原来的1664079次变为了57次
