AP计算机科学：含中间输出的双重递归调用执行时序求助

兄弟我太懂这种困惑了！当初第一次碰到这种夹着System.out.println的双重递归，我盯着控制台输出愣了十分钟，完全摸不着头脑😅。咱们拿一个具体的代码例子来拆解，一看就明白：

假设你遇到的是类似这样的代码：

public class DoubleRecursion {
    public static void recurse(int n) {
        if (n <= 0) {
            return; // 基准条件：终止递归
        }
        // 第一次递归调用（左分支）
        recurse(n - 1);
        // 中间的输出语句
        System.out.println(n);
        // 第二次递归调用（右分支）
        recurse(n - 1);
    }

    public static void main(String[] args) {
        recurse(2);
    }
}

咱们一步步走一遍执行流程，把调用栈的变化理清楚：

• 第一步：调用recurse(2)，n=2>0，先执行左分支的recurse(1)
  • 进入recurse(1)，n=1>0，执行左分支的recurse(0)
    • 进入recurse(0)，n<=0，直接返回，回到recurse(1)
  • 现在recurse(1)的左分支执行完了，执行中间的System.out.println(1)，控制台输出1
  • 然后执行recurse(1)的右分支recurse(0)，返回，回到recurse(2)
• 第二步：recurse(2)的左分支执行完了，执行中间的System.out.println(2)，控制台输出2
• 第三步：执行recurse(2)的右分支recurse(1)
  • 进入recurse(1)，执行左分支的recurse(0)，返回
  • 执行System.out.println(1)，控制台输出1
  • 执行右分支的recurse(0)，返回，整个流程结束

最终控制台的输出就是：

1
2
1

核心规律总结 #

这种结构的双重递归，执行顺序可以概括为：

1. 先把左分支递归到最底层（直到触发基准条件返回）
2. 执行当前层的中间输出/操作
3. 再把右分支递归到最底层

你可以把它想象成一棵二叉树：每个节点先遍历左子树到底，然后打印自己，再遍历右子树到底。画个树形图的话，一眼就能看明白调用和输出的顺序：

recurse(2)
       /         \
recurse(1)     recurse(1)
   /   \         /   \
recurse(0) recurse(0) recurse(0) recurse(0)

输出顺序就是左子树的节点→根节点→右子树的节点，也就是1→2→1。

如果还是懵，建议自己手动模拟n=1、n=3的情况，一步步写下来，很快就能摸透这个时序逻辑啦！

内容的提问来源于stack exchange，提问作者Rushil Vellala