当前位置：首页 > JavaScript

js实现简单递归

2026-02-03 03:20:32JavaScript

递归的基本概念

递归是一种通过函数调用自身来解决问题的方法。在JavaScript中，递归函数通常包含一个基线条件（终止条件）和递归条件（调用自身的条件）。

实现阶乘的递归函数

阶乘是递归的经典例子。阶乘的定义是：n! = n (n-1) (n-1) ... 1。

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

实现斐波那契数列的递归函数

斐波那契数列是另一个常见的递归例子，定义是：F(n) = F(n-1) + F(n-2)，且F(0) = 0，F(1) = 1。

function fibonacci(n) {
    if (n === 0) return 0;
    if (n === 1) return 1;
    return fibonacci(n - 1) + fibonacci(n - 2);
}
console.log(fibonacci(10)); // 输出: 55

递归遍历树形结构

递归在处理树形结构（如DOM树或嵌套对象）时非常有用。以下是一个遍历嵌套对象的例子：

const tree = {
    value: 1,
    children: [
        {
            value: 2,
            children: [
                { value: 4, children: [] },
                { value: 5, children: [] }
            ]
        },
        {
            value: 3,
            children: [
                { value: 6, children: [] }
            ]
        }
    ]
};

function traverse(node) {
    console.log(node.value);
    node.children.forEach(child => traverse(child));
}
traverse(tree); // 输出: 1, 2, 4, 5, 3, 6

递归的注意事项

递归虽然简洁，但需要注意栈溢出问题。如果递归深度过大，可能会导致调用栈溢出。可以通过尾递归优化或改用迭代来避免。

尾递归优化示例

尾递归是指递归调用是函数的最后一步操作。某些JavaScript引擎（如V8）支持尾调用优化（TCO）。

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

递归与迭代的对比

递归和迭代可以互相转换。例如，阶乘的迭代实现：

js实现简单递归

function factorialIterative(n) {
    let result = 1;
    for (let i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}
console.log(factorialIterative(5)); // 输出: 120

递归适合解决分治问题或树形结构遍历，而迭代更适合性能要求高的场景。