Optimize fibonacci sequence

题目: 求斐波那契数列 1,1,2,3,5,8,13,21,34,55,89...中的第 n 项

斐波那契数列考察的是递归算法, 但是要注意优化, 探寻下面优化前后的代码片段。

优化前:

let count1 = 0
function fn(n) {
count1++
if (n === 1 || n === 2) {
return 1
}
return fn(n - 1) + fn(n - 2)
}
console.log(fn(20), count1) // 6765 13529

优化后:

function _fn(n) {
if (cache[n]) {
return cache[n]
}
count2++
if (n === 1 || n === 2) {
return 1
}
cache[n - 1] = _fn(n - 1)
cache[n - 2] = _fn(n - 2)
return cache[n - 1] + cache[n - 2]
}
let count2 = 0
function fn(n) {
const cache = {}
return _fn(n)
}
console.log(fn(20), count2) // 6765 20

小结: 通过记忆化缓存数据, 可以看到大大提高了运行性能。