编辑“︁JavaScript递归优化”︁（章节）

= JavaScript递归优化 =

递归是函数式编程中的核心概念之一，但在JavaScript中，不当的递归使用可能导致性能问题。本章节将深入探讨递归优化的方法，包括尾调用优化（TCO）、记忆化（Memoization）和转换为迭代的实用技巧。

== 递归基础回顾 ==
递归是指函数直接或间接调用自身的过程。经典的例子是计算阶乘：

<syntaxhighlight lang="javascript">
function factorial(n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);  // 递归调用
}
console.log(factorial(5)); // 输出: 120
</syntaxhighlight>

这种递归虽然简洁，但存在两个主要问题：
1. 每次递归调用都会创建新的栈帧，可能导致栈溢出（Stack Overflow）
2. 重复计算相同参数时效率低下

== 尾递归优化 ==
=== 什么是尾调用 ===
当函数的最后一步是调用另一个函数（包括自身）时，称为'''尾调用'''。ES6规范要求实现尾调用优化（TCO），但截至2023年大多数JavaScript引擎仍未完全支持。

=== 尾递归实现 ===
将上述阶乘函数改写为尾递归形式：

<syntaxhighlight lang="javascript">
function factorial(n, acc = 1) {
    if (n <= 1) return acc;
    return factorial(n - 1, n * acc);  // 尾递归调用
}
console.log(factorial(5)); // 输出: 120
</syntaxhighlight>

关键改进：
* 引入累积参数（acc）保存中间结果
* 递归调用是函数的最后操作
* 在支持TCO的环境中，这种形式不会增加栈深度

=== 执行过程对比 ===
<mermaid>
graph TD
    A[常规递归 factorial(3)] --> B[3*factorial(2)]
    B --> C[2*factorial(1)]
    C --> D[返回1]
    C --> E[返回2*1=2]
    A --> F[返回3*2=6]

    G[尾递归 factorial(3,1)] --> H[factorial(2,3)]
    H --> I[factorial(1,6)]
    I --> J[返回6]
</mermaid>

== 记忆化优化 ==
记忆化（Memoization）通过缓存函数结果避免重复计算，特别适用于有重复子问题的递归。

=== 斐波那契数列案例 ===
未优化版本：
<syntaxhighlight lang="javascript">
function fibonacci(n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}
// 时间复杂度: O(2^n)
</syntaxhighlight>

记忆化优化版本：
<syntaxhighlight lang="javascript">
const memo = new Map();
function fibonacci(n) {
    if (memo.has(n)) return memo.get(n);
    if (n <= 1) return n;
    
    const result = fibonacci(n - 1) + fibonacci(n - 2);
    memo.set(n, result);
    return result;
}
// 时间复杂度: O(n)
</syntaxhighlight>

== 递归转迭代 ==
当递归深度可能很大时，转换为迭代是更安全的选择。

=== 通用转换方法 ===
1. 使用显式栈模拟调用栈
2. 将递归逻辑分解为循环步骤

=== 阶乘函数的迭代实现 ===
<syntaxhighlight lang="javascript">
function factorial(n) {
    let result = 1;
    for (let i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}
</syntaxhighlight>

=== 复杂递归的转换示例 ===
深度优先搜索（DFS）的递归与迭代对比：

递归版本：
<syntaxhighlight lang="javascript">
function dfs(node, visit) {
    visit(node);
    node.children.forEach(child => dfs(child, visit));
}
</syntaxhighlight>

迭代版本：
<syntaxhighlight lang="javascript">
function dfs(startNode, visit) {
    const stack = [startNode];
    while (stack.length) {
        const node = stack.pop();
        visit(node);
        // 注意子节点压栈顺序（保持原顺序需反转）
        stack.push(...node.children.reverse());
    }
}
</syntaxhighlight>

== 实际应用场景 ==
=== 目录树遍历 ===
处理嵌套的文件目录结构时，递归比迭代更直观：

<syntaxhighlight lang="javascript">
function traverseDir(dir, callback) {
    callback(dir);
    dir.getChildren().forEach(child => {
        if (child.isDirectory()) {
            traverseDir(child, callback);
        }
    });
}
</syntaxhighlight>

=== 无限滚动加载 ===
现代Web应用中的分页数据加载可视为递归过程，但需要转换为迭代实现以避免栈溢出：

<syntaxhighlight lang="javascript">
async function loadAllPages(startUrl) {
    let currentUrl = startUrl;
    while (currentUrl) {
        const { data, nextPageUrl } = await fetchPage(currentUrl);
        processData(data);
        currentUrl = nextPageUrl;
    }
}
</syntaxhighlight>

== 性能考量 ==
使用递归时需要考虑：
* 最大调用栈深度（通常约10,000-100,000次调用）
* 空间复杂度（调用栈占用）
* 时间复杂度（特别是存在重复计算时）

数学表达式表示普通递归的空间复杂度：
<math>
S(n) = O(n)
</math>

尾递归优化后的空间复杂度（在支持TCO的环境中）：
<math>
S(n) = O(1)
</math>

== 最佳实践建议 ==
1. 优先尝试将递归改写为尾递归形式
2. 对于树形结构等递归天然适合的场景，考虑：
   * 设置合理的递归深度限制
   * 对纯函数使用记忆化
3. 当递归深度不可预测时，转换为迭代实现
4. 使用调试工具分析调用栈和内存使用

== 总结 ==
JavaScript递归优化是函数式编程的重要技能。通过尾递归、记忆化和迭代转换等技术，可以在保持代码清晰度的同时解决性能问题。开发者应根据具体场景选择适当的优化策略，并注意不同JavaScript引擎对TCO的支持差异。

[[Category:编程语言]]
[[Category:JavaScript]]
[[Category:Javascript函数式编程]]