当前位置：首页 > JavaScript

js实现递归

2026-04-03 23:46:38JavaScript

递归的基本概念

递归是一种在函数内部调用自身的技术。通过将问题分解为更小的子问题，递归可以简化复杂问题的解决方案。在JavaScript中，递归函数需要包含基线条件（终止条件）和递归条件（继续调用自身的条件）。

递归函数的实现

定义一个递归函数时，必须确保存在终止条件，否则会导致无限循环和堆栈溢出。以下是实现递归的基本结构：

function recursiveFunction(parameters) {
    // 基线条件（终止递归）
    if (baseCase) {
        return baseValue;
    }
    // 递归条件（继续递归）
    return recursiveFunction(modifiedParameters);
}

示例：计算阶乘

阶乘是一个经典的递归问题。n!表示从1到n所有整数的乘积。

function factorial(n) {
    // 基线条件：0!或1!等于1
    if (n === 0 || n === 1) {
        return 1;
    }
    // 递归条件：n! = n * (n-1)!
    return n * factorial(n - 1);
}
console.log(factorial(5)); // 输出: 120

示例：斐波那契数列

斐波那契数列中每个数字是前两个数字之和（如0, 1, 1, 2, 3, 5...）。

function fibonacci(n) {
    // 基线条件：前两项直接返回
    if (n === 0) return 0;
    if (n === 1) return 1;
    // 递归条件：fib(n) = fib(n-1) + fib(n-2)
    return fibonacci(n - 1) + fibonacci(n - 2);
}
console.log(fibonacci(6)); // 输出: 8

尾递归优化

普通递归可能导致堆栈溢出，尤其是处理大数据时。尾递归是一种优化技术，通过确保递归调用是函数的最后操作来减少堆栈占用。

function factorialTailRecursive(n, accumulator = 1) {
    if (n === 0) return accumulator;
    return factorialTailRecursive(n - 1, n * accumulator);
}
console.log(factorialTailRecursive(5)); // 输出: 120

递归与循环的选择

递归代码通常更简洁，但可能效率较低。循环（如for或while）在性能敏感的场景中更优。例如，斐波那契数列的循环实现：

function fibonacciIterative(n) {
    if (n === 0) return 0;
    let a = 0, b = 1;
    for (let i = 2; i <= n; i++) {
        [a, b] = [b, a + b];
    }
    return b;
}
console.log(fibonacciIterative(6)); // 输出: 8

递归的注意事项

堆栈溢出：深度递归可能超出调用堆栈限制，导致错误。
性能问题：某些递归（如朴素斐波那契）会重复计算，可通过记忆化（缓存结果）优化。
调试难度：递归逻辑可能比循环更难调试，建议使用调试工具逐步跟踪。

递归的实际应用

递归适合解决分治问题（如树遍历、快速排序）或具有自相似结构的问题（如目录遍历）。例如，遍历嵌套对象：

js实现递归

function traverseObject(obj) {
    for (let key in obj) {
        if (typeof obj[key] === 'object') {
            traverseObject(obj[key]);
        } else {
            console.log(key + ": " + obj[key]);
        }
    }
}
const nestedObj = { a: 1, b: { c: 2, d: { e: 3 } } };
traverseObject(nestedObj);