当前位置：首页 > JavaScript

js 实现递归

2026-01-16 12:07:59JavaScript

递归的基本概念

递归是指函数直接或间接调用自身的过程。在JavaScript中，递归通常用于解决可以分解为相似子问题的问题，如阶乘、斐波那契数列、树形结构遍历等。

递归的实现要点

基线条件（Base Case） 递归必须有一个终止条件，否则会导致无限循环。基线条件是递归停止的条件，通常是问题的最简单情况。

递归条件（Recursive Case） 递归条件将问题分解为更小的子问题，并调用自身处理这些子问题。

递归示例：计算阶乘

阶乘是一个经典的递归问题。n的阶乘（n!）定义为n乘以(n-1)的阶乘，且0! = 1。

function factorial(n) {
    if (n === 0) { // 基线条件
        return 1;
    }
    return n * factorial(n - 1); // 递归条件
}

console.log(factorial(5)); // 输出: 120

递归示例：斐波那契数列

斐波那契数列的第n项是前两项之和，且第0项为0，第1项为1。

function fibonacci(n) {
    if (n <= 1) { // 基线条件
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2); // 递归条件
}

console.log(fibonacci(6)); // 输出: 8

递归的优缺点

优点

代码简洁，易于理解。
适合处理树形结构或分治问题。

缺点

可能引发栈溢出（Stack Overflow），尤其是递归深度较大时。
性能较低，因为每次递归调用都会占用额外的内存。

尾递归优化

尾递归是指递归调用是函数的最后一步操作。某些JavaScript引擎（如ES6严格模式下的V8）支持尾调用优化（TCO），可以避免栈溢出。

function factorialTail(n, acc = 1) {
    if (n === 0) {
        return acc;
    }
    return factorialTail(n - 1, n * acc); // 尾递归
}

console.log(factorialTail(5)); // 输出: 120

递归与循环的对比

递归和循环可以互相替代。递归更直观，但循环通常性能更好且不易栈溢出。

// 循环实现阶乘
function factorialLoop(n) {
    let result = 1;
    for (let i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}

console.log(factorialLoop(5)); // 输出: 120

实际应用：遍历树形结构

递归非常适合处理树形结构，如DOM遍历或嵌套对象。

function traverseDOM(node) {
    console.log(node.nodeName);
    const children = node.childNodes;
    for (let i = 0; i < children.length; i++) {
        traverseDOM(children[i]); // 递归遍历子节点
    }
}

traverseDOM(document.body); // 遍历整个DOM树