js递归实现fnah

递归实现斐波那契数列（Fibonacci）的方法

递归是一种通过函数调用自身来解决问题的方法。斐波那契数列是一个经典的递归案例，其定义如下：

• 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);
}

这种方法简单直观，但效率较低，因为会重复计算许多子问题。例如，计算 fibonacci(5) 时会多次计算 fibonacci(2)。

优化递归（带记忆化）

通过存储已计算的结果避免重复计算，可以显著提高性能。

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

memo 对象用于缓存已计算的值，减少重复调用。

尾递归优化

某些 JavaScript 引擎支持尾递归优化（TCO），可以避免栈溢出问题。

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

尾递归通过将中间结果传递给下一次调用，减少栈空间的使用。

注意事项

• 基础递归的时间复杂度为 O(2^n)，记忆化优化后为 O(n)。
• 对于较大的 n（如 n > 50），基础递归可能导致栈溢出或性能问题，建议使用记忆化或迭代方法。
• 递归代码更简洁，但迭代（循环）实现通常性能更好。