合并排序函数中的两个递归调用混淆

Question

我已经与算法脱节了一段时间,并且最近开始修改我的概念.令我惊讶的是,最后我记得我的递归技巧是我很擅长但不再了.所以,我有一个基本问题,你们这让我很困惑.请先看下面的代码..

private void mergesort(int low, int high) {
    if (low < high) {
        int middle = (low + high)/2 ;
        System.out .println ("Before the 1st Call");
        mergesort(low, middle);
        System.out .println ("After the 1st Call");
        mergesort(middle+1, high);
        System.out .println ("After the 2nd Call");
        merge(low, middle, high);
    }
}

函数调用

mergesort(0,7);

输出是

在第一次通话之前

在第一次通话之前

在第一次通话之前

第一次通话后

第二次通话后

第一次通话后

在第一次通话之前

第一次通话后

第二次通话后

第二次通话后

第一次通话后

在第一次通话之前

在第一次通话之前

第一次通话后

第二次通话后

第一次通话后

在第一次通话之前

第一次通话后

第二次通话后

第二次通话后

第二次通话后

令我困惑的是上面的代码和结果是第二次递归调用.我理解流程直到第四个输出线(即:第一次调用后).但我无法理解为什么它(在第一次通话后)输出(第二次通话后).根据代码的理解,在输出之后(第一次调用之后)应该调用带参数(中间+ 1,高)的mergesort函数,它应该输出(在第一次调用之前)并使用mergesort进入递归调用(低,中).我熟悉一个递归调用函数并理解并与foreg fibonacci示例同步.

Answer 1

在第四个输出行,您已从第一个调用和随后的2个递归调用返回,因此现在控制到达 System.out .println ("After the 1st Call");

因此,在low < high第二次递归调用之后条件为false,因此您只需退出该函数.然后,控制在第二次递归调用之后立即返回到该行.

提示 学习递归时我常常做的一件事就是跟踪堆栈深度(例如传入一个参数),然后在输出中根据堆栈深度缩进输出.这有助于您可视化递归链中的位置,并使调试更容易.

因此,您的调试输入可能类似于以下内容:

entered method, low = 0, high = 10
  entered method, low = 0, high = 5
     entered method, low = 0, high = 2
     exiting method, low = 0, high = 2
  exiting method, low = 0, high = 5
exiting method, low = 0, high = 10

Answer 2

只需按照执行......

First call 0,7 --> enters if, middle = 3 (integer division), calls again as (0,3)
Second call 0,3 --> enters if, middle = 1, calls again as (0,1)
Third call 0,1 --> enters if, middle = 0, calls again as (0,0)
Fourth call 0,0 --> does not enter if, back to third call
Third call 0,1 --> calls as middle+1,high which is (1,1)
Fifth call 1,1 --> does not enter if, back to third call
Third call 0,1 --> calls the string you didn't expect

可以继续,但这是你不希望执行的字符串.