斐波拉契

斐波那契数列 1, 1, 2,3,5,8,13,21….. 使用公式f( n ) = f(n-1)+f(n-2),结束条件f(2) =1, f(1) = 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

    //初始实现
    function fib(n) {
        if( n==1 || n == 2){
            return 1;
        }
        else{
            return fib(n-1)+fib(n-2);
        }
    }


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

    // for 循环实现

    function fib(n){
        var res = [1,1];
        if( n==1 || n == 2){
            return 1;
        }
        for(var i=2; i<n; i++){
            res.push(res[i-1]+res[i-2]);
        }
        return res[n-1];
    }


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

    var cache = [];
    function fib(n){        
        if(cache[n] !== undefined){               
            return cache[n];
        }          
        if(n <= 2){               
            cache[n] = 1;
            return 1;
        }    
        cache.push(fib(n - 1) + fib(n - 2));
        return cache[n];
    }