当前位置：首页 > JavaScript

js 递归实现

2026-02-01 23:12:39JavaScript

递归的基本概念

递归是一种通过函数调用自身来解决问题的方法。在JavaScript中，递归通常用于处理具有重复结构的问题，如树遍历、阶乘计算等。

递归实现阶乘

阶乘是一个经典的递归示例。n的阶乘（n!）是所有小于或等于n的正整数的乘积。

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);
}

递归实现数组求和

递归也可以用于对数组中的元素求和。

function sumArray(arr, index = 0) {
    if (index === arr.length) {
        return 0;
    }
    return arr[index] + sumArray(arr, index + 1);
}

递归实现深度拷贝

递归可以用于实现对象的深度拷贝，确保嵌套对象也被正确拷贝。

function deepCopy(obj) {
    if (typeof obj !== 'object' || obj === null) {
        return obj;
    }
    let copy = Array.isArray(obj) ? [] : {};
    for (let key in obj) {
        copy[key] = deepCopy(obj[key]);
    }
    return copy;
}

递归实现目录遍历

在处理文件系统或类似结构时，递归可以用于遍历嵌套的目录结构。

function traverseDirectory(dir) {
    dir.forEach(item => {
        if (item.isDirectory) {
            traverseDirectory(item.children);
        } else {
            console.log(item.name);
        }
    });
}

递归的注意事项

递归虽然强大，但需要注意避免无限递归和栈溢出。确保递归有明确的终止条件，并且对于大规模数据，考虑使用尾递归优化或迭代替代。

尾递归优化

尾递归是一种特殊的递归形式，可以被某些JavaScript引擎优化以避免栈溢出。

js 递归实现

function factorialTailRecursive(n, accumulator = 1) {
    if (n === 0) {
        return accumulator;
    }
    return factorialTailRecursive(n - 1, n * accumulator);
}