合并排序函数混淆中的两个递归调用 [英] Two recursive calls in a Merge Sort function confusion

问题描述

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

I have been out of touch with Algorithms for a while and have start revising my concepts these days. To my surprise the last i remember of my recursions skill was that i was good at it but not anymore. So, i have a basic question for you guys which is confusing me. Please see the below code first ..

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

输出

在第一次通话之前

Before the 1st Call

在第一次通话之前

在第一次通话之前

第一次通话后

第二次通话后

第一次通话后

第一次通话前

第一次通话后

第二次通话后

第二次通话后

第一次通话后

在第一次通话之前

在第一次通话之前

第一次通话后

第二次通话后

第一次通话后

第一次通话前

第一次通话后

第二次通话后致电

第二次通话后

第二次通话后

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

The thing confusing me in the above code and result is the second recursive call. I am understanding the flow until the fourth output line ( i.e : After the 1st Call). But i cannot understand why does it outputs ( After the 2nd Call ) after the ( After the 1st Call ). According to whati am understanding from the code After the output ( After the 1st Call ) the mergesort function with parameter (middle+1, high) should be called and it should output ( Before the 1st call ) and go into the recursive call with mergesort (low, middle). I am comfartable with one recursive call functions and understand and am sync with foreg fibonacci example .

推荐答案

在第四个输出行，你已经从第一次调用和随后的2次递归调用返回，所以现在控件到达 System.out .println（第一次调用后）;

On the fourth output line, you have returned from the first call and the subsequent 2 recursive calls, so now control reaches the System.out .println ("After the 1st Call");

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

So, the condition low < high is false after the second recursive call, so you just exit the function. Then, control returns to the line right after the second recursive call.

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

TIP One thing I used to do when learning recursion is to keep track of stack depth (e.g. pass in a parameter for this) and then on your output you indent your output based on stack depth. This helps you visualize where you are in the recursive chain, and makes debugging easier.

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

So your debugging input could look similar to the following:

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

这篇关于合并排序函数混淆中的两个递归调用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！