斐波那契数列

题目描述

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。
n<=39

代码如下：

function Fibonacci(n){
    if(n<=1){
          return n;
    }else{
          return Fibonacci(n-1) + Fibonacci(n-2);
}
}

结果报错了：

错误.PNG

后来发现是因为重复的计算：
因为f(1)和f(0)都是未知的，所以一直重复计算f(1)和f(0)的值

function Fibonacci(n)
{
    var arr = [];
    arr[0] = 0;
    arr[1] = 1;
    for(var i=2;i <= n;i++){
        arr[i] = arr[i-1] + arr[i-2];
    }
    return arr[n];
    // write code here
}
module.exports = {
    Fibonacci : Fibonacci
};