1.递归
function fib(n){
    if(n==1||n==2){
        return 1;
    }
    return fbnq(n-1)+fbnq(n-2);
}
fbnq(10);
//55

时间复杂度为O(2^n),空间复杂度为O(n)


2.非递归

function fb(n){
    var res = [1,1];
    if(n == 1 || n == 2){
        return 1;
    }      
    for(var i=2;i

时间复杂度为O(n),空间复杂度为O(n)


3.非递归

function fb(n){
    var a,b,res;
    a = b = 1;
    for(var i=3;i<=n;i++){
        res = a + b;
        a = b;
        b = res;
    }
    return res;
}
fb(10);

//55
时间复杂度为O(n),空间复杂度为O(1)