斐波那契数列

求斐波那契数列第n个数

方法一

最直观的方法

function fibonacci1(n) {
    if (n <= 1) {
        return 1
    } else {
        return fibonacci2(n - 1) + fibonacci2(n - 2)
    }
}

方法二

在方法一基础上尾递归优化

function fibonacci2(n, ac1 = 1, ac2 = 2) {
    if (n <= 1) {
        return 1
    } else {
        fibonacci3(n-1, ac2, ac1 + ac2)
    }
}

方法三

function fibonacci3(n) {
    const arr = [];
    let i = 0;
    while(i <= n) {
        if (i <= 1) {
            arr[i] = 1
        } else {
            arr[i] = arr[i -1] + arr[i-2]
        }
        i++;
    }

    return arr
}