递归是一种编程技巧，其中一个函数调用自身来解决同一问题的较小实例。它非常适合具有自相似结构的任务，例如浏览文件夹、遍历树/DOM，或将问题分解为更小的子问题（分而治之）。
如果递归让你感觉抽象，那么本指南将使它变得实用。你将了解如何安全地编写递归函数，它们在哪些方面表现突出，何时应该避免使用它们，以及如何提高它们的速度。
您将学到什么
什么是递归以及它在 JavaScript 中如何工作
每个递归函数的两个基本部分（基本情况和递归情况）
常见示例：阶乘、斐波那契数列、嵌套数据遍历和树/DOM 遍历
性能和内存影响（以及如何避免堆栈溢出）
记忆化和将递归转换为迭代等技术
最佳实践和简单的调试技巧
什么是递归？
在编程中，递归是指一个函数使用较小的输入调用自身，直到遇到一个作为停止点的基准情况。
任何递归函数都有两个部分：
基本情况：停止递归。
递归情况：简化问题并再次调用该函数。如果任何一部分缺失或不正确，则可能会陷入无限递归或堆栈溢出。
递归函数的剖析（模板）
function solve(problem) {
if (isSimple(problem)) {
// 1) Base case
return simpleAnswer(problem);
}
// 2) Recursive case
const smaller = reduce(problem);
return combine(solve(smaller));
}把这个心理模板放在手边；你会经常重复使用它。
示例 1：阶乘（递归简介）
n! = n × (n − 1) × ... × 1；根据定义 0! = 1
function factorial(n) {
if (n < 0) throw new Error("n must be >= 0");
if (n === 0) return 1; // base case
return n * factorial(n - 1); // recursive case
}
console.log(factorial(5)); // 120要避免的陷阱：忘记基本情况或让 n 为负数。
示例 2：斐波那契数列（朴素算法 vs. 记忆算法）
第 n 个斐波那契数定义为：
F(0) = 0, F(1) = 1
F(n) = F(n − 1) + F(n − 2)
朴素（简单但缓慢）
function fib(n) {
if (n < 0) throw new Error("n must be >= 0");
if (n <= 1) return n; // base cases
return fib(n - 1) + fib(n - 2); // overlapping subproblems!
}记忆化（快速且仍然递归）
缓存结果以避免重新计算：
const fibMemo = (function () {
const memo = new Map([[0, 0], [1, 1]]);
return function f(n) {
if (n < 0) throw new Error("n must be >= 0");
if (memo.has(n)) return memo.get(n);
const value = f(n - 1) + f(n - 2);
memo.set(n, value);
return value;
};
})();
console.log(fibMemo(40)); // fast要点：如果递归导致对相同子问题的重复工作，则通过添加记忆或将其转换为动态规划来优化它。
示例 3：嵌套数组的总和（使用分层数据）
function sumNested(arr) {
let total = 0;
for (const item of arr) {
if (Array.isArray(item)) total += sumNested(item); // recurse into sub-array
else total += item;
}
return total;function sumNested(arr) {
let total = 0;
for (const item of arr) {
if (Array.isArray(item)) total += sumNested(item); // recurse into sub-array
else total += item;
}
return total;
}
console.log(sumNested([1, [2, [3, 4]], 5]));
}
console.log(sumNested([1, [2, [3, 4]], 5])); // 15递归非常适合解决涉及分层或树形结构的问题。
示例 4：遍历树（深度优先搜索）
const tree = {
value: "A",
children: [ {
value: "B",
children: [{
value: "D", children: []
}]
},
{
value: "C",
children: [{
value: "E",
children: []
},
{
value: "F",
children: []
}]
}
]};
function dfs(node, visit) {
if (!node) return;
visit(node);
for (const child of node.children) {
dfs(child, visit);
}
}
dfs(tree, (n) => console.log(n.value)); // A B D C E F这种模式反映了许多现实世界的任务，例如浏览文件夹或处理 JSON 树。
DOM 遍历（浏览器上下文）
您可以使用递归方法遍历浏览器中的 DOM。
function countTextNodes(node) {
if (!node) return 0;
let count = node.nodeType === Node.TEXT_NODE ? 1 : 0;
for (const child of node.childNodes) {
count += countTextNodes(child);
}
return count;
}
// Example: countTextNodes(document.body)注意：这仅在具有 DOM 的环境中运行（浏览器、一些测试工具）。
递归与迭代（何时使用哪个）
在以下情况下优先使用递归：
数据是分层的（树、嵌套列表、DOM、AST）。
该算法遵循分而治之策略，如快速排序和归并排序所示。
您正在进行回溯（排列、组合、路径查找）。
在以下情况下优先使用迭代：
您正在对平面数据进行简单的循环。
深度可能非常大（堆栈溢出的风险）。
性能/内存至关重要，递归会增加开销。
将递归 DFS 转换为迭代（使用堆栈）
function dfsIterative(root, visit) {
if (!root) return;
const stack = [root];
while (stack.length) {
const node = stack.pop();
visit(node);
if (node.children) {
// push right-to-left so left is processed first
for (let i = node.children.length - 1; i >= 0; i--) {
stack.push(node.children[i]);
}
}
}
}性能、堆栈深度和尾调用
调用堆栈限制：深度递归可能导致 RangeError：超出最大调用堆栈大小。限制因环境和输入大小而异。
尾递归：ES2015 规定了正确的尾调用，但大多数 JavaScript 引擎在实践中并未优化尾递归。为了安全起见，不要依赖它。
通过记忆、深度限制或迭代重写来提高递归的效率。
调试递归函数
使用缩进记录来可视化调用堆栈：
function factorialTrace(n, depth = 0) {
const indent = " ".repeat(depth);
console.log(`${indent}factorial(${n})`);
if (n === 0) return 1;
const result = n * factorialTrace(n - 1, depth + 1);
console.log(`${indent}→ ${result}`);
return result;
}先测试小输入，然后扩大规模。
使用单元测试框架（例如 Jest 或 Vitest）来确认您的基本案例是否有效。
最佳实践清单
始终指定明确的基准情况以确保递归正确停止。
每次递归调用都应缩小问题规模，以便最终达到基本情况。
防止无效输入
避免在递归中改变共享/全局状态
使用记忆法解决重叠子问题
对于分层数据和回溯，优先使用递归
如果深度较大或性能受到影响，则切换到迭代
添加跟踪日志或单元测试来验证行为
结论
JavaScript
中的递归是解决自然分解问题的强大工具，尤其适用于分层数据、分治算法和回溯。关键在于编写可靠的基础用例，确保每一步都能简化问题，并使用诸如记忆化之类的技术来管理性能，或在必要时切换到迭代方法。
通过本指南中的模式和示例、阶乘、斐波那契数列、嵌套结构和树形遍历，您现在拥有了清晰实用的基础，可以在实际项目中自信而安全地应用递归。