当前位置：首页 > JavaScript

js如何实现递归函数

2026-01-31 00:24:27JavaScript

递归函数的基本概念

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

实现递归函数的要点

基线条件（Base Case）
递归必须有一个明确的终止条件，否则会导致无限循环。例如，计算阶乘时，0的阶乘定义为1，这就是基线条件。
递归条件（Recursive Case）
在递归条件中，函数调用自身，并逐步向基线条件靠近。例如，计算n的阶乘时，递归条件是n * factorial(n - 1)。

示例1：计算阶乘

function factorial(n) {
    if (n === 0) { // 基线条件
        return 1;
    } else { // 递归条件
        return n * factorial(n - 1);
    }
}
console.log(factorial(5)); // 输出120

示例2：斐波那契数列

斐波那契数列的第n项是前两项之和，基线条件是第1项和第2项为1。

function fibonacci(n) {
    if (n <= 1) { // 基线条件
        return n;
    } else { // 递归条件
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}
console.log(fibonacci(6)); // 输出8

示例3：遍历树形结构

递归非常适合处理嵌套数据结构，例如树或目录。

const tree = {
    name: "root",
    children: [
        {
            name: "child1",
            children: [
                { name: "grandchild1", children: [] },
                { name: "grandchild2", children: [] }
            ]
        },
        { name: "child2", children: [] }
    ]
};

function traverse(node) {
    console.log(node.name);
    node.children.forEach(child => traverse(child)); // 递归遍历子节点
}
traverse(tree); // 输出root, child1, grandchild1, grandchild2, child2

递归的注意事项

堆栈溢出
递归调用会占用堆栈空间，如果递归深度过大（如未正确设置基线条件），可能导致堆栈溢出错误。
性能优化
某些递归问题（如斐波那契数列的朴素递归）会重复计算，可以通过记忆化（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];
}
console.log(fibonacciMemo(50)); // 快速计算大数

尾递归优化

某些语言（如ES6的严格模式）支持尾递归优化，避免堆栈溢出。JavaScript引擎的实现支持有限，但可以手动模拟。

js如何实现递归函数

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