斐波那契数列的求法

斐波那契数列如下:

0，1，1，2，3，5，8，13，21，34，55，...

该序列为数列的当前项为此当前项的前两项之和。即：

recurFib(n) = recurFib(n-1)+recurfib(n-2);

递归方式

递归方式思考比较简单由上面的公式直接得出，难点在于边界值的判断。但是这个算法本身的计算会产生一个二叉数组，数组的节点在某些值上会重复，所以可以对这个算法进行改进。以避免重复运算

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

}


console.log(recurFib(10));//55

动态规划版

function iterFib(n) {
    var last = 1;
    var nextLast = 1;
    var result = 1;

    if(n==0) {
        return 0;
    }
    
    for(var i =2 ; i < n ;i ++) {
        result = last+nextLast;
        nextLast = last;
        last = result;
    }

    return result;
}

总结：

就比较而言动态规划法去掉了一些重复步骤，加快了运行速度