斐波那契数列js 实现

1. 暴力实现

function fibonacci(n) {

    if (!(/^[1-9]\d*$/.test(n))) {

        throw new Error("请输入正整数！")

    }

    if (n == 0) return 0

    if (n == 1) return 1

    return fibonacci(n - 1) + fibonacci(n - 2)

}

2. 闭包优化,加入缓存（空间 换时间）

function fibonacci2() {
    let cache = [0, 1, 1]

    function fib(n) {
        console.log(this);
        if (cache[n]) {
            return cache[n]
        }

        if (n <= 2) {
            //把计算结果存入数组
            return cache[n];
        }

        var temp = fib(n - 1) + fib(n - 2);
        //把计算结果存入数组
        cache[n] = temp;

        // console.log(cache);
        return temp;
    }

    return fib;
}

3. 时间换空间。for循环

function fibonacci4(n) {
    var res1 = 1;
    var res2 = 1;
    var sum = res2;
    for (var i = 2; i < n; i++) {
        sum = res1 + res2;
        res1 = res2;
        res2 = sum;
    }
    return sum;
}

4. 尾部优化递归调用

function fibonacci4(n, res1 = 1, res2 = 1) {

    if (!(/^[1-9]\d*$/.test(n))) {

        throw new Error("请输入正整数！")

    }

    if (n <= 2) {

        return res2;

    } else {

        return fibonacci4(n - 1, res2, res1 + res2);

    }

}

本作品采用《CC 协议》，转载必须注明作者和本文链接