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

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，高）的合并排序函数，它应该输出（在第一次调用之前）并使用合并排序进入递归调用（低，中）。我对一个递归调用函数很满意，并且理解并与前斐波那契示例同步。

score 17 · Accepted Answer

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

因此，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

score 5 · Accepted Answer

跟着执行就行了...

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

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

score 2 · Accepted Answer

2

你也可以打印出highand的值low。遵循递归会容易得多。

于 2012-06-22T14:18:43.167 回答

score 1 · Accepted Answer

尝试打印middle变量的值。

最佳实践要求您不要在没有任何变量输出的情况下使用“函数前”样式的调试消息进行编码。

score 1 · Accepted Answer

在输出 4 行后 low = 0, middle = 0, high = 1 所以调用 mergesort(middle+1,high) 不会打印任何内容（ 1 < 1 为假）

score 1 · Accepted Answer

下面的缩进对应于递归：

mergesort(0, 7)
    middle=3
    "Before the 1st Call"
    mergesort(0, 3)
        middle=1
        "Before the 1st Call"
        mergesort(0, 1)
            middle=0
            "Before the 1st Call"
            mergesort(0, 0)
                (0 < 0) is false so return
        "After the 1st Call"
        mergesort(1, 1)
            (1 < 1) is false so return
        "After the 2nd Call"

        etc ...

score 1 · Accepted Answer

运行这段代码可以很好地理解递归。我已经考虑了控制台中的堆栈深度。希望它能让它易于理解！

    #include "stdafx.h"
    #include <iomanip>
    using namespace std;
    static int stackdepth=0;
    void mergesort(int[],int,int);
    void merge(int[],int,int,int);
    void  space(int);
    int main(int argc,char *argv[])
    {
        int a[8]={5,7,1,4,9,3,2,0};
        mergesort(a,0,7);
        for(int i=0;i<10;i++)
    //  cout<<a[i]<<endl;
        return 0;
    }
    void mergesort(int a[],int low,int high)
    {
        int mid;

        if(low<high)
        {

            mid=(low+high)/2;
            space(stackdepth);
            cout<<"First Recursion Enter";
            cout<<" Low :"<<low<<" Mid :"<<mid<<endl;
            stackdepth++;
            mergesort(a,low,mid);
            stackdepth--;
            space(stackdepth);
            cout<<"First Recursion Exit";
            cout<<" Low :"<<low<<" Mid :"<<mid<<endl;
            space(stackdepth);
            stackdepth++;
            cout<<"Second Recursion Enter";
            cout<<" Mid+1 :"<<mid+1<<" High :"<<high<<endl;
            mergesort(a,mid+1,high);
            stackdepth--;
            space(stackdepth);
            cout<<"Second Recursion Exit";
            cout<<" Low :"<<mid+1<<" High :"<<high<<endl;
            space(stackdepth);
            cout<<"Merge Low :"<<low<<" Mid :"<<mid<<"High :"<<high<<endl;
            merge(a,low,mid,high);
            cout<<endl;
            space(stackdepth);
            cout<<"------------------------------------------------------------------------------------------"<<endl;
        }
    }
    void space(int stackdepth)
    {
        for(int i=0;i<stackdepth;i++)
        cout<<"                     ";

    }
    void merge(int a[],int low,int mid,int high)
    {
    //  cout<<endl;
    //  cout<<"Merging Begins"<<endl;
        int b[8];
        int i,k,j;
        i=low;k=low;j=mid+1;
        while(i<=mid && j<=high)
        {
            if(a[i]<a[j])
            {
                    b[k++]=a[i++];
            }
            else
            {
                b[k++]=a[j++];
            }
        }
        while(i<=mid)
            b[k++]=a[i++];
        while(j<=high)
            b[k++]=a[j++];
        space(stackdepth);
        for(int i=low;i<=high;i++)
        {
            a[i]=b[i];
        cout<<a[i]<<" ";
        }
            //cout<<"Low :"<<low<<" Mid :"<<mid<<" High :"<<high<<endl;
        //  cout<<"Merging Ends"<<endl;
        //  cout<<endl;
    }

score 0 · Accepted Answer

合并排序使用递归算法来创建高度为 Log N 的完整二叉树，其中 N 是该树的节点数（这就是为什么如此高效的原因）。在下一张图片中，您可以逐步看到针对您的案例执行此算法的流程，以及创建的二叉树（我认为这是了解其工作原理的最佳方式）：

使用包含 8 个位置的数组的合并排序生成的二叉树

合并排序所做的是将数组递归地分成两半，首先到最低的一半，直到我们到达一个单一元素，然后从最近到达的最低元素中分割出较高的一半。这就是为什么它每次调用都会调用自己两次，以便创建一个完整的二叉树，当我们到达一个单元（带有叶节点）时停止，只有在我们有两个单元（带有父节点）时才合并。在下图中，您可以逐步查看数组是如何递归拆分的：

使用合并排序逐步划分 8 个元素的数组

score 0 · Accepted Answer

0

转到eclipse调试工具。按照步骤，你会发现规则双递归。我就是做这个的。

于 2017-05-10T03:39:25.927 回答

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

9 回答 9

Related

Reference