Java递归代码输出解析求助：splitIt函数执行结果存疑

代码示例 #

public class Main {
    public static void main(String[] args) {
        splitIt(1, 3);
    }

    public static void splitIt(int id, int n) {
        if (n > 0) {
            splitIt(id + 1, n - 1);
            System.out.println(id + "=" + n);
            splitIt(id + 1, n - 1);
        }
    }
}

运行输出 #

3=1
2=2
3=1
1=3
3=1
2=2
3=1

执行流程拆解 #

递归的核心逻辑是先深入左分支调用，再执行打印操作，最后深入右分支调用，我们逐层追踪执行过程：

1. 初始调用：splitIt(1, 3)

   • 因n=3>0，优先执行第一个递归：splitIt(2, 2)

2. 进入splitIt(2, 2)

   • 因n=2>0，优先执行第一个递归：splitIt(3, 1)

3. 进入splitIt(3, 1)

   • 因n=1>0，优先执行第一个递归：splitIt(4, 0)
     • n=0不满足条件，直接返回
   • 执行打印：3=1（输出第一行）
   • 执行第二个递归：splitIt(4, 0)，直接返回
   • splitIt(3,1)执行完毕，回到splitIt(2,2)

4. 回到splitIt(2,2)

   • 执行打印：2=2（输出第二行）
   • 执行第二个递归：splitIt(3,1)
     • 重复步骤3的逻辑：先调用splitIt(4,0)返回，打印3=1（输出第三行），再调用splitIt(4,0)返回
   • splitIt(2,2)执行完毕，回到splitIt(1,3)

5. 回到splitIt(1,3)

   • 执行打印：1=3（输出第四行）
   • 执行第二个递归：splitIt(2,2)
     • 重复步骤2-4的逻辑：
       • 调用splitIt(3,1)打印3=1（第五行）
       • 回到splitIt(2,2)打印2=2（第六行）
       • 调用splitIt(3,1)打印3=1（第七行）
   • 所有递归执行完毕，程序结束

你可以把每个splitIt(id,n)看作二叉树的一个节点：左、右子节点都是splitIt(id+1,n-1)，打印语句是节点的内容。整个执行过程就是先遍历左子树，输出节点，再遍历右子树，最终得到的输出顺序完全对应二叉树的中序遍历结果。

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