面试题：JavaScript中递归函数的基本实现

Question

请使用JavaScript编写一个递归函数，用于计算斐波那契数列的第n项。斐波那契数列的定义为：F(0) = 0, F(1) = 1, F(n) = F(n - 1) + F(n - 2) （n > 1）。并简要说明递归函数在这个场景中的优缺点。

Answer 1

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

递归函数在这个场景中的优点

1. 代码简洁：递归的实现方式能够非常直观地反映出斐波那契数列的数学定义，代码量少，逻辑清晰。

递归函数在这个场景中的缺点

1. 效率低下：会进行大量重复计算，例如计算 fibonacci(5) 时，fibonacci(3) 会被计算两次，随着 n 的增大，重复计算量呈指数级增长，导致时间复杂度为 $O(2^n)$。
2. 容易栈溢出：由于递归调用会占用栈空间，当 n 较大时，递归的深度可能会超出JavaScript引擎的栈容量，导致栈溢出错误。