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

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

middle = 0, high = 1, поэтому вызов функции mergesort (middle + 1, high) ничего не печатает (1 & lt; 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;
    }

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

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

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

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

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

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

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

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

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

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

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