斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)

递归

  1. function f(n){
  2.   if(n==1){
  3.     return 1
  4.   }
  5.   else if(n==2){
  6.     return 2
  7.   } else {
  8.     return f(n-1) + f(n-2)
  9. }

上边的过程

递推

  1. /**
  2.  * @param {number} n
  3.  * @return {number}
  4.  */
  5. var fib = function(n) {
  6.     var cache = []
  7.     for(var i = 0; i <= n; i++){
  8.         if (i === 0 || i === 1){
  9.             cache[i] = i
  10.         } else {
  11.             cache[i] = cache[i-1] + cache[i-2]
  12.         }
  13.     }
  14.     return cache[n]
  15. };