递归

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)

非递归

##　１
function fb(n){
var res = [1,1];
if(n == 1 || n == 2){
return 1;
}
for(var i=2;i<n;i++){
res[i] = res[i-1] + res[i-2];
}
return res[n-1];
}
fb(10);
//55

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

2

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)

质数

function foo(n){  
  var a=[],state=0;  
  for(var i=2;i<n;i++){  
    var sqrt_i = Math.sqrt(i);  
    if(i%sqrt_i===0){  
      continue;  
    }  
    for(var j=2;j<sqrt_i;j++){  
      if(i%j===0){  
        state=1;  
        break;  
      }else{  
        state=0;  
      }  
    }  
   if(state===0){  
     a.push(i);  
   }  
  }  
  console.log(a);  
}  
foo(100)

无穷的斐波那契数列

//"无穷"的菲波纳契数据结构  
function Fib(n, x, y)  
{  
    //这里借参数x,y来保留前面的计算结果，即菲波数当前数列到n的最后两个数值  
    //在实际调用中通常并不用到x、y这两个参数  
    var a = x || 1;  
    var b = y || 1;  
    if(n == 0) b = a;  

    var t;  

    //计算菲波数的算法  
    for(var i = 2; i <= n + 1; i++)  
    {  
        t = b;  
        b = a + b;  
        a = t;  
    }  

    var ret = function(n, x, y){    
        //构造一个闭包，这个闭包本身包含一个以新起点计算Fib值的函数  
        x = x || a;  
        y = y || b;  
        return Fib(n, x, y);  
    }  

    //重写valueOf和toString，这样在表达式中可以直接对返回的菲波函数自动求值  
    //在第五部分我们还会详细讨论到这种用法  
    ret.valueOf = ret.toString = function()  
    {  
        return a;  
    }  
    return ret;  
}  
var f6 = Fib(6);  //奥妙在这里，f6是一个新起点的菲波数列函数  
dwn(f6);  
dwn(f6(4));