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

java recursion

2022-09-04 07:16:11

我已经与算法脱节了一段时间，这些天开始修改我的概念。令我惊讶的是，我对递归技能的最后记忆是我擅长它，但现在不行了。所以，我有一个基本问题要问你们，这让我感到困惑。请先查看以下代码..

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);

输出是

第一次通话前

第一次通话前

第一次通话前

第一次通话后

第二次通话后

第一次通话后

第一次通话前

第一次通话后

第二次通话后

第二次通话后

第一次通话后

第一次通话前

第一次通话前

第一次通话后

第二次通话后

第一次通话后

第一次通话前

第一次通话后

第二次通话后

第二次通话后

第二次通话后

在上面的代码和结果中，让我感到困惑的是第二个递归调用。我正在理解流程，直到第四条输出线（即：在第一次调用之后）。但我不明白为什么它输出（在第二次呼叫之后）之后（在第一次呼叫之后）。根据代码的理解，在输出之后（第一次调用之后），应该调用带有参数（middle+1，high）的mergesort函数，它应该输出（在第1次调用之前），并使用mergesort（低，中）进入递归调用。我与一个递归调用函数兼容，并理解并与前斐波那契示例同步。

答案 1

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

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

提示在学习递归时，我曾经做过的一件事是跟踪堆栈深度（例如，为此传入一个参数），然后在输出上根据堆栈深度缩进输出。这有助于您可视化递归链中的位置，并使调试更容易。

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

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

答案 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

可以继续，但这是执行您不期望的字符串的地方。