什么是递归？ 🤔

递归就是函数调用自身的过程。就像是一个套娃，每一层都在解决同样的问题，只是规模越来越小。

递归的思维误区 ⚠️

1. 陷入调用栈的思维陷阱：不要试图在脑中追踪每一次函数调用
2. 过度关注细节：应该把注意力放在问题的分解上
3. 没有明确的终止条件：这会导致无限递归

写好递归的三步法 📝

1. 确定终止条件：什么情况下停止递归（防止死循环）
2. 递归主体：每一次递归具体在做什么
3. 返回值设计：需要向上一层返回什么数据

经典示例与详解 🌟

1. 求二叉树的最大深度

function getMaxDepth(root) {
    // 终止条件：树为空就终止
    if (root === null) return 0;
    
    // 递归主体：
    // 1. 获取左子树的深度
    // 2. 获取右子树的深度
    const leftDepth = getMaxDepth(root.left);
    const rightDepth = getMaxDepth(root.right);
    
    // 返回值：
    // 比较左右子树的深度，取较大值，然后加上当前节点的深度1
    return Math.max(leftDepth, rightDepth) + 1;
}

2. 两两交换链表中的节点

function swapPairs(head) {
    // 终止条件：
    // 链表为空或只有一个节点时，无法交换，直接返回
    if (head === null || head.next === null) {
        return head;
    }
    
    // 递归主体：
    // 1. 保存第二个节点
    // 2. 处理后续节点
    // 3. 交换前两个节点
    const temp = head.next;
    head.next = swapPairs(temp.next);  // 递归处理后续节点
    temp.next = head;
    
    // 返回值：
    // 返回新的头节点（原来的第二个节点）
    return temp;
}

3. 判断平衡二叉树

class ReturnNode {
    constructor(depth, isBalanced) {
        this.depth = depth;         // 记录当前子树的高度
        this.isBalanced = isBalanced; // 记录是否是平衡树
    }
}

// 主函数：对外暴露简单的接口
function isBalanced(root) {
    return checkBalance(root).isBalanced;
}

// 递归函数：实际的递归逻辑
function checkBalance(root) {
    // 终止条件：
    // 空树也是平衡树，高度为0
    if (root === null) return new ReturnNode(0, true);
    
    // 递归主体：
    // 1. 检查左子树
    // 2. 检查右子树
    const left = checkBalance(root.left);
    const right = checkBalance(root.right);
    
    // 如果任意子树不平衡，整棵树就不平衡
    if (!left.isBalanced || !right.isBalanced) {
        return new ReturnNode(0, false);
    }
    
    // 检查高度差是否超过1
    if (Math.abs(left.depth - right.depth) > 1) {
        return new ReturnNode(0, false);
    }
    
    // 返回值：
    // 当前子树平衡时，返回其高度和平衡状态
    return new ReturnNode(
        Math.max(left.depth, right.depth) + 1,
        true
    );
}

递归优化技巧 💡

1. 记忆化递归

// 斐波那契数列的记忆化递归实现
const memo = new Map();

function fib(n) {
    // 检查是否已经计算过
    if (memo.has(n)) return memo.get(n);
    
    // 基础情况
    if (n <= 1) return n;
    
    // 计算并存储结果
    const result = fib(n - 1) + fib(n - 2);
    memo.set(n, result);
    
    return result;
}

实践注意事项 ⚡️

1. 调试技巧

   • 先验证基础情况是否正确
   • 使用小规模输入测试
   • 打印递归层级帮助理解

2. 性能考虑

   • 注意递归深度限制
   • 考虑是否需要记忆化
   • 某些场景可以用循环替代

3. 代码风格

   • 保持递归函数的单一职责
   • 使用清晰的变量命名
   • 添加必要的注释说明

总结 🎯

递归不仅是一种编程技巧，更是一种解决问题的思维方式。掌握好"三步法"，避开常见误区，就能写出优雅且高效的递归代码。记住：递归的关键在于将复杂问题分解为相似的子问题，而不是纠结于函数调用的细节。