面试题：JavaScript 中递归函数实现斐波那契数列

Question

请使用JavaScript递归函数实现斐波那契数列，并说明递归实现可能存在的性能问题及原因。斐波那契数列指的是这样一个数列：0、1、1、2、3、5、8、13、21、34 、…… ，在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）。

Answer 1

使用JavaScript递归函数实现斐波那契数列

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

递归实现可能存在的性能问题及原因

1. 性能问题：递归实现斐波那契数列在计算较大的n值时，性能会急剧下降，计算时间会变得非常长，甚至导致栈溢出错误。
2. 原因：
   • 重复计算：在递归过程中，会有大量的重复计算。例如计算fibonacci(5)时，fibonacci(3)会被计算两次，fibonacci(2)会被计算多次。随着n的增大，重复计算的数量呈指数级增长。
   • 栈空间消耗：每次函数调用都会在栈中分配空间，递归调用层次过深会导致栈空间被耗尽，从而引发栈溢出错误。