js如何实现递归

递归的基本概念

递归是一种函数调用自身的技术。在JavaScript中，递归通常用于解决可以被分解为更小同类问题的情况，例如遍历树结构、计算阶乘等。

实现递归的基本步骤

定义一个函数，在函数内部调用自身。递归必须包含终止条件，否则会导致无限循环。

function factorial(n) {
    if (n === 0 || n === 1) { // 终止条件
        return 1;
    }
    return n * factorial(n - 1); // 递归调用
}

递归的终止条件

终止条件是递归的关键部分，确保递归不会无限进行下去。例如，计算斐波那契数列时：

function fibonacci(n) {
    if (n <= 1) { // 终止条件
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2); // 递归调用
}

递归的性能优化

递归可能导致性能问题，尤其是重复计算。可以使用记忆化（Memoization）来优化：

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

递归的替代方案

某些情况下，递归可以用循环替代，以避免堆栈溢出：

function factorialIterative(n) {
    let result = 1;
    for (let i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

递归的适用场景

递归适合解决分治问题，如树遍历、汉诺塔等。例如，遍历DOM树：

function traverseDOM(node) {
    console.log(node);
    for (let child of node.children) {
        traverseDOM(child); // 递归遍历子节点
    }
}

递归的注意事项

递归可能导致堆栈溢出，尤其是在处理大规模数据时。现代JavaScript引擎支持尾调用优化（TCO），但并非所有环境都支持。

function tailRecursion(n, acc = 1) {
    if (n === 1) return acc;
    return tailRecursion(n - 1, n * acc); // 尾递归优化
}