js中递归实现
递归的基本概念
递归是一种函数调用自身的编程技术，通常用于解决可分解为相似子问题的问题。在JavaScript中，递归需要满足两个条件：基线条件（终止条件）和递归条件（继续调用自身的条件）。
递归的实现步骤
定义基线条件
基线条件是递归终止的前提，防止无限循环。例如计算阶乘时，0的阶乘是1，因此基线条件可以是 if (n === 0) return 1。
定义递归条件
递归条件将问题分解为更小的子问题。例如阶乘的递归条件是 return n * factorial(n - 1)，每次调用函数时参数逐步接近基线条件。
递归的经典示例
计算阶乘
function factorial(n) {
if (n === 0) return 1; // 基线条件
return n * factorial(n - 1); // 递归条件
}
console.log(factorial(5)); // 输出 120斐波那契数列
function fibonacci(n) {
if (n <= 1) return n; // 基线条件
return fibonacci(n - 1) + fibonacci(n - 2); // 递归条件
}
console.log(fibonacci(6)); // 输出 8递归的注意事项
堆栈溢出风险
递归可能因调用层级过深导致堆栈溢出。可通过尾递归优化（部分引擎支持）或改用循环（迭代）解决。
性能问题
某些递归（如朴素斐波那契）会重复计算子问题，效率低。可结合备忘录模式（缓存结果）优化。
尾递归优化示例
尾递归指递归调用是函数的最后操作，部分JavaScript引擎可优化其堆栈使用。
function factorialTail(n, acc = 1) {
if (n === 0) return acc;
return factorialTail(n - 1, acc * n); // 尾递归
}
console.log(factorialTail(5)); // 输出 120递归与迭代的选择
- 递归更直观，适合问题天然具有递归结构（如树遍历）。
- 迭代（循环）通常性能更高，适合需要避免堆栈溢出的场景。
通过合理设计基线条件和递归条件，递归能简洁地解决复杂问题，但需注意性能和堆栈限制。
