当前位置：首页 > JavaScript

js递归实现fnah

2026-04-07 12:37:57JavaScript

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

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

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

以下是使用 JavaScript 递归实现斐波那契数列的代码：

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

优化递归实现（备忘录模式）

由于纯递归实现的时间复杂度为 O(2^n)，效率较低，可以通过备忘录模式（Memoization）优化性能：

function fibonacciMemo(n, memo = {}) {
    if (n in memo) return memo[n];
    if (n === 0) return 0;
    if (n === 1) return 1;
    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);
}

注意事项

性能问题：纯递归实现的时间复杂度为 O(2^n)，不适用于大数值计算。
堆栈溢出：递归深度过大可能导致堆栈溢出，建议使用迭代或备忘录模式优化。
边界条件：确保处理 n 为 0 或 1 的情况，避免无限递归。

迭代实现（对比）

如果递归性能不足，可以使用迭代实现：

js递归实现fnah

function fibonacciIterative(n) {
    if (n === 0) return 0;
    if (n === 1) return 1;
    let a = 0, b = 1;
    for (let i = 2; i <= n; i++) {
        let temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

递归实现斐波那契数列适合教学和理解递归原理，但在实际应用中建议使用优化版本或迭代实现。