js实现递归
递归的基本概念
递归是一种通过函数调用自身来解决问题的方法。在JavaScript中，递归通常用于处理具有重复子问题或分治结构的数据，例如树形结构、阶乘计算等。
递归的实现要点
-
基线条件（Base Case）
递归必须有一个明确的终止条件，否则会导致无限循环。例如，计算阶乘时，0的阶乘定义为1。 -
递归条件（Recursive Case）
函数需要调用自身，并将问题分解为更小的子问题。例如，n! = n * (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递归的注意事项
-
堆栈溢出
递归会占用调用堆栈空间，深度过大会导致堆栈溢出。可以通过尾递归优化（Tail Call Optimization）或改用循环解决。 -
性能问题
某些递归（如斐波那契数列的朴素实现）会重复计算子问题，效率低下。可以使用备忘录（Memoization）优化。
尾递归优化示例
尾递归是指递归调用是函数的最后一步操作。某些JavaScript引擎会优化尾递归，避免堆栈溢出。
function factorialTail(n, acc = 1) {
if (n === 0) {
return acc;
}
return factorialTail(n - 1, acc * n); // 尾递归调用
}
console.log(factorialTail(5)); // 输出: 120递归的实际应用
遍历树形结构
function traverseTree(node) {
console.log(node.value);
if (node.children) {
node.children.forEach(child => traverseTree(child));
}
}
const tree = {
value: 1,
children: [
{ value: 2, children: [{ value: 4 }] },
{ value: 3 }
]
};
traverseTree(tree); // 输出: 1, 2, 4, 3递归与循环的对比
递归代码通常更简洁，但可能不如循环高效。选择递归还是循环取决于具体问题和性能需求。对于复杂嵌套结构（如树、图），递归通常是更自然的选择。
