js递归实现fnah

递归实现斐波那契数列

斐波那契数列是一个经典的递归案例，数列定义如下：

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2) （n ≥ 2）

基础递归实现

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

这个实现简单直观，但效率较低，因为会重复计算相同的子问题。

带缓存的递归实现

通过添加缓存来存储已计算的结果，避免重复计算：

function fibonacciMemo(n, memo = {}) {
    if (n in memo) return memo[n];
    if (n <= 1) return n;
    memo[n] = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
    return memo[n];
}

这种方法显著提高了性能，时间复杂度从指数级降低到线性级。

尾递归优化实现

某些JavaScript引擎支持尾调用优化，可以使用尾递归形式：

function fibonacciTail(n, a = 0, b = 1) {
    if (n === 0) return a;
    if (n === 1) return b;
    return fibonacciTail(n - 1, b, a + b);
}

注意事项

递归实现虽然简洁，但需要注意：

• 基础递归实现对于较大的n值会导致栈溢出
• 带缓存的实现需要额外的内存空间
• 尾递归优化不一定在所有JavaScript环境中都支持

对于生产环境，迭代实现通常是更好的选择，特别是需要处理大数时。