递归学习遇阻：Java每日DSA挑战中多分支递归执行流程困惑

1. 先抓递归核心：「终止条件」+「当前层逻辑」+「递归子问题」 #

不管单分支还是多分支，递归本质都是这三点——多分支只是子问题有多个而已。别一开始就盯着整个调用栈空想，先聚焦当前函数要做什么。

拿二叉树前序遍历（多分支递归典型）举例：

public void preOrder(TreeNode root) {
    // 终止条件：当前节点为空，直接返回
    if (root == null) {
        return;
    }
    // 当前层逻辑：访问当前节点
    System.out.println(root.val);
    // 递归子问题1：遍历左子树
    preOrder(root.left);
    // 递归子问题2：遍历右子树
    preOrder(root.right);
}

这里的多分支就是同时递归左、右子树，记住规则：当前函数执行完自身逻辑后，会先把第一个分支的递归全跑完，再回头处理下一个分支。

2. 用小例子手动跟踪执行流程 #

拿上面的二叉树例子，假设树结构是：

1
   / \
  2   3

一步步拆解执行顺序：

1. 调用preOrder(1)：不为空，打印1，接着调用preOrder(2)
2. 调用preOrder(2)：不为空，打印2，调用preOrder(2.left)（为空）
3. preOrder(2.left)触发终止条件，返回
4. 回到preOrder(2)，继续调用preOrder(2.right)（为空）
5. preOrder(2.right)触发终止条件，返回
6. preOrder(2)执行完毕，返回
7. 回到preOrder(1)，继续调用preOrder(3)
8. 调用preOrder(3)：不为空，打印3，调用preOrder(3.left)（为空）
9. preOrder(3.left)返回，回到preOrder(3)，调用preOrder(3.right)（为空）
10. preOrder(3.right)返回，preOrder(3)执行完毕，返回
11. preOrder(1)执行完毕，整个流程结束

这种小例子跟踪2-3次，就能摸透多分支的执行规律——每一个分支都会被「深度优先」执行完，再回到上一层处理下一个分支。

3. 把递归调用当成「黑盒」 #

别纠结子递归内部怎么跑，先假设它能完成任务。比如求二叉树最大深度：

public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    // 默认左子树的最大深度能正确返回
    int leftDepth = maxDepth(root.left);
    // 默认右子树的最大深度能正确返回
    int rightDepth = maxDepth(root.right);
    // 当前层逻辑：取左右深度最大值加1（当前节点的深度）
    return Math.max(leftDepth, rightDepth) + 1;
}

你不需要去想maxDepth(root.left)内部的计算细节，只需要处理当前层的逻辑，以及确保终止条件正确。

4. 避免陷入调用栈迷宫的小技巧 #

• 写递归代码时先写终止条件，这是递归的“出口”，没出口不仅会栈溢出，还会让流程更难梳理。
• 用注释明确区分「当前层逻辑」和「递归子问题」，避免代码混在一起。
• 复杂多分支场景（比如回溯），可以在递归前后加打印语句，直观看到调用顺序：

public void backtrack(int[] nums, List<Integer> path) {
    System.out.println("进入：" + path);
    if (path.size() == nums.length) {
        System.out.println("找到结果：" + path);
        return;
    }
    for (int num : nums) {
        if (path.contains(num)) continue;
        path.add(num);
        backtrack(nums, path);
        path.remove(path.size() - 1);
    }
    System.out.println("退出：" + path);
}

运行后看打印的进入、退出记录，能清晰看到每个分支的调用和回溯过程。

内容的提问来源于stack exchange，提问作者Yogendra Singh