当前位置：首页 > JavaScript

js如何实现递归函数

2026-04-04 16:17:15JavaScript

递归函数的基本概念

递归函数是指在函数内部调用自身的函数。递归通常用于解决可以被分解为相同问题的子问题的情况，如阶乘、斐波那契数列等。

递归函数的实现步骤

定义一个递归函数需要明确两个部分：基线条件（递归终止条件）和递归条件（继续调用自身的条件）。

基线条件是递归停止的条件，防止无限递归导致栈溢出。递归条件是函数继续调用自身的条件，通常会将问题分解为更小的子问题。

示例：计算阶乘

阶乘是一个经典的递归问题，n! = n * (n-1)!，其中 0! = 1 是基线条件。

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

示例：斐波那契数列

斐波那契数列的递归定义是 fib(n) = fib(n-1) + fib(n-2)，基线条件是 fib(0) = 0 和 fib(1) = 1。

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

递归的注意事项

递归可能导致性能问题，尤其是当递归深度较大时。例如，斐波那契数列的递归实现会重复计算很多子问题，效率较低。可以通过记忆化（缓存已计算的结果）优化。

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)); // 高效计算

尾递归优化

某些语言支持尾递归优化（TCO），但JavaScript引擎的实现有限。尾递归是指递归调用是函数的最后一步操作。

js如何实现递归函数

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