Вопрос по java, recursion – Два рекурсивных вызова в путанице функции сортировки слиянием

13

Некоторое время я не общался с Алгоритмами и сейчас начинаю пересматривать свои концепции. К моему удивлению, последнее, что я помню о своих навыках рекурсии, было то, что я был хорош в этом, но не больше Итак, у меня есть основной вопрос для вас, ребята, который сбивает меня с толку. Пожалуйста, сначала посмотрите код ниже.

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

Before the 1st Call

Before the 1st Call

After the 1st Call

After the 2nd Call

After the 1st Call

Before the 1st Call

After the 1st Call

After the 2nd Call

After the 2nd Call

After the 1st Call

Before the 1st Call

Before the 1st Call

After the 1st Call

After the 2nd Call

After the 1st Call

Before the 1st Call

After the 1st Call

After the 2nd Call

After the 2nd Call

After the 2nd Call

В приведенном выше коде и результате меня смущает второй рекурсивный вызов. Я понимаю последовательность до четвертой строки вывода (т.е. после 1-го вызова). Но я не могу понять, почему он выводит (после 2-го вызова) после (после 1-го вызова). Согласно тому, что я понимаю из кода После вывода (после 1-го вызова) должна быть вызвана функция слияния с параметром (middle + 1, high), и она должна вывести (до 1-го вызова) и перейти к рекурсивному вызову с помощью mergesort (низкий, средний). Я совместим с одним рекурсивным вызовом функций и понимаю и синхронизируюсь с примером Форе Фибоначчи.

Попробуйте дать ему меньшее число, а затем проследите через вывод. Это может сделать его немного легче увидеть. John Kane
Используйте отладчик! не этот печатный мусор! Colin D

Ваш Ответ

9   ответов
1

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 1s,t Call"
        mergesort(1, 1)
            (1 < 1) is false so return
        "After the 2nd Call"

        etc ...
1

middle = 0, high = 1, поэтому вызов функции mergesort (middle + 1, high) ничего не печатает (1 & lt; 1 ложно)

1

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

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

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

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

Это тот же ответ, который я получил. Ручка и бумага могут помочь, но следуйте за этим с отладчиком, чтобы действительно сделать это простым.
1

middle переменная.

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

0

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

17

х рекурсивных вызовов, так что теперь управление достигаетSystem.out .println ("After the 1st Call");

Итак, состояниеlow < high ложь после второго рекурсивного вызова, поэтому вы просто выходите из функции. Затем управление возвращается на линию сразу после второго рекурсивного вызова.

TIP Одна вещь, которую я использовал при изучении рекурсии, - это отслеживание глубины стека (например, передача параметра для этого), а затем на выходе вы делаете отступ в зависимости от глубины стека. Это помогает вам визуализировать, где вы находитесь в рекурсивной цепочке, и облегчает отладку.

Таким образом, ваш отладочный ввод может выглядеть примерно так:

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
+1 за отслеживание глубины стека.
@LivingThing вы можете отслеживать глубину стека, передавая ее третьему параметру mergesort (int low, int high, int глубине), увеличивая глубину на 1 каждый раз, когда выполняется рекурсивный вызов.
Спасибо DCP, я понимаю твой ответ. Что касается СОВЕТА, я не получил его. Я гуглил это, но это также не показало никаких окончательных ответов. Так что я создам новую тему для него. LivingThing
0

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

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

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

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

2

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

твердый совет, но было бы лучше просто шаг за шагом использовать отладчик. тогда у него есть доступ ко всем данным!

Похожие вопросы