2.4.1 递归和循环

面试题10：斐波那契数列
递归会存在大量的重复数据。按照如下进行优化

<script>
    function Fibonacci(n)
    {
        if(n===0)
            return 0;
        if(n===1)
            return 1;
        let num1=0;
        let num2=1;
        let fibN;
    for(let i=2;i<=n;i++){
        fibN=num1+num2;
        num1=num2;
        num2=fibN;
    }
        return fibN;
    }
</script>

题目二:跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法.

function jumpFloor(number)
{
    let F1=1;
    let F2=2;
    if(number===1)
        return 1;
    if(number===2)
        return 2;
    let Fn; 
    for(let i=3;i<=number;i++){
        Fn=F1+F2;
        F1=F2;
        F2=Fn;
    }
    return Fn;
}

题目三：变态跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
假设最后跳1阶 f(n-1)种；最后跳2阶 f(n-2)种；...最后跳n阶 1种
f(n)=f(n-1)+f(n-2)+....+1;

function jumpFloorII(number)
{
    // write code here
    if(number===1)
    return 1;
    if(number===2)
     return 2;
    let f1=1;
    let f2=2;
    for(let i=3;i<=number;i++){
        fn=f1+f2+1;
        f1=f1+f2;
        f2=fn;
    }
    return fn;
}

题目四：覆盖矩形

我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

function rectCover(number)
{
    if(number===0)
        return 0;
    // write code here
    //覆盖一个方框有一种方法
    if(number===1)
        return 1;
    //覆盖两个有2种.横着覆盖，竖着覆盖
    if(number===2)
        return 2;
    let f1=1;
    let f2=2;
    let fn;
    for(let i=3;i<=number;i++){
        fn=f1+f2;
        f1=f2;
        f2=fn;
    }
    return fn;
}