如何优化这段JS递归斐波那契函数的代码执行效率？

原代码的核心问题是递归过程中会重复计算大量重叠子问题，比如计算fib(5)的时候会重复计算fib(3)两次、fib(2)三次，时间复杂度达到O(2ⁿ)，下面是几种可落地的优化方案： #

方案1：记忆化缓存（改动最小，保持递归写法） #

给对象加一个缓存容器，存储已经计算过的n对应的结果，下次遇到相同的n直接从缓存取，不需要重复计算，优化后时间复杂度降到O(n)。

var yourself = {
    // 提前存入边界值的缓存
    cache: {0: 0, 1: 1},
    fibonacci : function(n) {
        // 缓存命中直接返回
        if (this.cache[n] !== undefined) return this.cache[n]
        // 未命中就计算后存入缓存再返回
        const res = this.fibonacci(n - 1) + this.fibonacci(n - 2)
        this.cache[n] = res
        return res
    }
};

如果不想把缓存暴露为对象的可访问属性，也可以用闭包把缓存隐藏起来：

var yourself = {
    fibonacci: (function() {
        const cache = {0: 0, 1: 1}
        return function(n) {
            if (cache[n] !== undefined) return cache[n]
            cache[n] = this.fibonacci(n-1) + this.fibonacci(n-2)
            return cache[n]
        }
    })()
}

方案2：迭代实现（无递归栈溢出风险，性能最优） #

直接从底往上累加计算，完全没有递归的函数调用开销，也不会因为n过大触发递归栈溢出，时间复杂度O(n)，空间复杂度可以降到O(1)，适合计算很大的n值。

var yourself = {
    fibonacci : function(n) {
        if (n === 0) return 0
        if (n === 1) return 1
        let prevPrev = 0, prev = 1, current
        for (let i = 2; i <= n; i++) {
            current = prevPrev + prev
            prevPrev = prev
            prev = current
        }
        return prev
    }
};

方案3：尾递归优化（依赖JS运行环境支持） #

把中间计算结果放到递归参数里传递，保证每次递归调用是函数的最后一个操作，符合ES6尾递归优化规则的环境会自动把递归转换成循环，不会触发栈溢出。

var yourself = {
    fibonacci : function(n, prevPrev = 0, prev = 1) {
        if (n === 0) return prevPrev
        if (n === 1) return prev
        return this.fibonacci(n - 1, prev, prevPrev + prev)
    }
};

注意：尾递归优化仅在ES6严格模式下的部分运行环境生效，比如Node.js、Safari，Chrome和Firefox目前默认不开启该特性，生产环境优先选择前两种方案。 #

内容的提问来源于stack exchange，提问作者Rasheed abiodun