如何优化递归斐波那契函数以提高性能？

Question

我创建了一个递归函数来计算斐波那契数，但对于较大的

n

值来说，它的速度非常慢。我知道效率低下是由于多次重新计算相同的斐波那契值。如何提高该算法的性能？

我使用了基本的递归方法

function fibonacci(n) {
    if (n <= 1) {
        return n;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

虽然这种方法有效，但由于冗余计算，时间复杂度很高。我可以做什么来优化它以获得更大的

n

值？

Answer 1

分配一个包含存储值的数组。

Fibonacci(n) 如果可能则返回存储的值，否则进行递归调用并存储该值。这以恒定的时间运行。