裴波那契数列基础版与优化版

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次