js获取菲波那契数列的第N个元素

概序

菲波那契数列，大致可以描叙为a(n) = a(n-1) + a(n-2) (a > 2)。类似于这样[1, 1, 2, 3, 5, 8, 13 ...]，下面我们用js来实现一下：

1.递归

var a = function(n) {
   if (n === 1 || n === 2) {
       return 1
   } else {
       return a(n - 1) + a(n - 2)
   }
}
console.time('a（44）')
console.log(a(44))
console.timeEnd('a（44）')

以上我们可以比较清晰的看出代码的思路，但是这种方法有一个致命的缺点：效率太差！

执行到第44个的时候，已经不能接受了。需要5s多。那我们再来改进一下:

2.闭包+缓存

var b = (function() {
   var cache = {
       1: 1,
       2: 1
   }
   return function(n) {
       if (cache[n]) {
           return cache[n]
       } else {
           cache[n - 1] = b(n - 1)
           cache[n - 2] = b(n - 2)
           return cache[n - 1] + cache[n - 2]
       }
   }
})()

console.time('b（1200）')
console.log(b(1200))
console.timeEnd('b（1200）')

将每一步计算出来的值，保存到了缓存中。效率提升了许多：

3.直接计算出该数列的值得数组，然后再从数组中取值

var c = function(n) {
   var arr = [1, 1]
   if (n === 1 || n === 2) {
       return 1
   }
   for (var i = 2; i < n; i ++) {
       arr[i] = arr[i - 1] + arr[i - 2]
   }
   return arr[n - 1]
}

console.time('c（1200）')
console.log(c(1200))
console.timeEnd('c（1200）')

这样效率又进一步提高了不少：

4.直接使用数学表达式

从网上得出菲波那契数列是有数学表达式的：

var d = function(n) {
   return (1/(Math.pow(5, 1/2))) * (Math.pow((1 + Math.pow(5, 1/2))/2, n) - Math.pow((1 - Math.pow(5, 1/2))/2, n))
}

console.time('d（1200）')
console.log(d(1200))
console.timeEnd('d（1200）')