有这样一组数列： 0 、1、1、2、3、5、8、13、21….
我们管这个数列叫做斐波那契是咧，特点是数列的第n项总等于前两项适合。
现在我们需要知道第n项的斐波那契数是多少，都有哪些方法呢？

1、递归

第一反应的fibs应该是这样的

function fibs(n) {
  return n <=1  ? n : fibs(n - 1) + fibs(n - 2)
}

Good！这样计算固然没错，那么，这是不是最优解呢？
要讨论一个算法的优劣，毫无疑问，要看一下时间复杂度。递归的时间复杂度为O(2^n)

为什么是O(2^n)？我们以n=10举例。
来看下图！

通过上图，我们不仅可以看到，递归计算的复杂度，还可以看到在计算过程中，存在大量的重复计算！
What？
那想一下，我们能不能不去重复计算，怎么做。首先想到的方法——缓存

2、缓存递归

下面，我们来设置一个数组来缓存已经递归出的数据

var cache = []
function fibs(n) {
  if(n <= 1) {
    return n
  } else {
    if(!cache[n - 1]) {
      cache[n-1] = fibs(n - 1)
    }
    if(!cache[n - 2]) {
      cache[n-2] = fibs(n - 2)
    }
    return cache[n-1] + cache[n-2]
  }
}

通过以上方法将每一次递归的数据缓存在数组里，确实省去了一部分重复的计算。
重复计算去掉后，我们的时间复杂度变为多少了呢，细细想来，应该是——O(n)
那么除了缓存，还有没有更好的方法呢？

3、动态规划

function fibs(n) {
  let val = new Array(n).fill(0)
  if (n <= 2) {
    return 1
  } else {
    val[1] = 1
    val[2] = 2
    for (var i = 3; i <= n; ++i) {
      val[i] = val[i-1] + val[i-2]
    }
    console.log(val)
    return val[n]
  }
}