3.实现斐波那契数列

// F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）
// 0 1 1 2 3 5 8...
//实现斐波那契数列

//1.使用递归
function fib(n){
    if (n < 2){
        return n
    } else {
        return fib(n -1) + fib(n -2)
    }
}

//2.不使用递归
function fib1(n){
    if (n < 2){
        return n
    } else {
        let pre = 1
        let current = 1
        let res = 1
        for (let j = 2; j < n; j++){
            res = pre + current
            pre = current
            current = res
        }
        return res
    }
}

let i = 0
while (i < 10){
    console.log(fib1(i))
    i++
}
console.log('第21项: ', fib(20))