Два рекурсивных вызова в замешательстве функции Merge Sort

Ответ 1

На четвертой выходной строке вы вернулись с первого вызова и последующих двух рекурсивных вызовов, поэтому теперь управление достигает 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

Ответ 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

может продолжаться, но именно там выполняется строка, которую вы не ожидаете.

Ответ 3

Вы также можете распечатать значения high и low. Было бы намного легче следовать рекурсии.

Ответ 4

Попробуйте распечатать значение переменной middle.

Лучшая практика диктует, что вы не кодируете сообщения отладки стиля "Перед функцией" без каких-либо выходных данных.

Ответ 5

После 4 строк вывода low = 0, middle = 0, high = 1, поэтому вызов mergesort (средний + 1, высокий) не будет печатать ничего (1 < 1 - false)

Ответ 6

Отступ в следующем соответствует рекурсии:

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 ...

Ответ 7

Запустите этот кусок кода, чтобы хорошо понять рекурсию. Я рассмотрел глубину стека в консоли. Надеюсь, это упростит понимание!

    #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;
    }

Ответ 8

Merge Sort использует рекурсивный алгоритм для создания полного двоичного дерева с высотой журнала N, являющегося N числом узлов этого дерева (поэтому он настолько эффективен). На следующем изображении вы можете шаг за шагом увидеть, каков поток выполнения этого алгоритма для вашего случая, с созданным бинарным деревом (которое, я думаю, является лучшим способом понять, как оно работает):

Двоичное дерево, которое создается с помощью Merge Sort с массивом из 8 позиций

Что Merge Sort делает, так это разделить массив пополам рекурсивно, перейдя сначала к наименьшим половинам, пока мы не достигнем одного унитарного элемента, а затем переходим и разделяем более высокие из самого недавно полученного элемента. Вот почему он вызывает себя два раза за каждый предыдущий вызов, чтобы создать полное двоичное дерево, которое останавливается, когда мы достигаем одной единицы (с листовыми узлами) и только сливаем, когда у нас есть два (с родительскими узлами). На следующем рисунке вы можете увидеть, как ваш массив разбивается рекурсивно, шаг за шагом:

Пошаговое разделение массива из 8 элементов с помощью Merge Sort

Ответ 9

Перейдите в инструмент отладки eclipse. Следуйте шагу, и вы найдете двойную рекурсию правила. То, что я делаю.