Hai cuộc gọi đệ quy trong một chức năng Hợp nhất sắp xếp nhầm lẫn

Question

Tôi đã không liên lạc được với Thuật toán trong một thời gian và đã bắt đầu sửa đổi các khái niệm của mình trong những ngày này. Trước sự ngạc nhiên của tôi, lần cuối tôi nhớ về kỹ năng thu thập của tôi là tôi đã giỏi nhưng không còn nữa. Vì vậy, tôi có một câu hỏi cơ bản cho các bạn, điều khiến tôi khó hiểu. Xin vui lòng xem mã bên dưới đầu tiên ..

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

Chức năng gọi

mergesort(0,7); 

Và đầu ra là

Trước Call 1st

Trước Call 1st

Trước cuộc gọi đầu tiên

Sau Gọi 1

Sau khi cuộc gọi thứ 2

Sau Gọi 1

Trước Call 1st

Sau Gọi 1

Sau khi cuộc gọi thứ 2

Sau cuộc gọi thứ hai

Sau Gọi 1

Trước Call 1st

Trước Call 1st

Sau Gọi 1

Sau khi cuộc gọi thứ 2

Sau Gọi 1

Trước cuộc gọi đầu tiên

Sau Gọi 1

Sau khi cuộc gọi thứ 2

Sau khi cuộc gọi thứ 2

Sau khi cuộc gọi thứ 2

Điều khó hiểu cho tôi trong đoạn code trên và kết quả là lần thứ hai gọi đệ quy. Tôi hiểu luồng cho đến dòng đầu ra thứ tư (ví dụ: Sau lần gọi đầu tiên). Nhưng tôi không thể hiểu tại sao nó kết quả đầu ra (sau khi gọi 2) sau khi (sau khi gọi 1). Theo whati am hiểu từ mã Sau khi đầu ra (Sau khi gọi 1) chức năng mergesort với tham số (giữa + 1, cao) nên được gọi và nó nên đầu ra (Trước khi gọi 1) và đi vào cuộc gọi đệ quy với mergesort (thấp, trung bình). Tôi đang comfartable với một chức năng gọi đệ quy và hiểu và đồng bộ với ví dụ foreg fibonacci.

Answer 1

Trên dòng đầu ra thứ tư, bạn đã trở về từ cuộc gọi đầu tiên và 2 cuộc gọi đệ quy tiếp theo, vì vậy bây giờ kiểm soát đạt đến System.out .println ("After the 1st Call");

Vì vậy, điều kiện low < high là sai sau khi cuộc gọi đệ quy thứ hai, vì vậy bạn chỉ thoát khỏi hàm. Sau đó, kiểm soát trở lại dòng ngay sau cuộc gọi đệ quy thứ hai.

TIP Một điều tôi đã từng làm khi học đệ quy là để theo dõi chồng chiều sâu (ví dụ vượt qua trong một tham số cho việc này) và sau đó vào đầu ra của bạn, bạn thụt đầu ra của bạn dựa trên ngăn xếp chiều sâu. Điều này giúp bạn hình dung bạn đang ở đâu trong chuỗi đệ quy và làm cho việc gỡ lỗi dễ dàng hơn.

Vì vậy, đầu vào gỡ lỗi của bạn có thể trông giống như sau:

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 

Answer 2

Thử in giá trị của biến middle.

Thực tiễn tốt nhất quy định rằng bạn không mã hóa thông báo gỡ lỗi kiểu "Trước khi chức năng" mà không có bất kỳ đầu ra biến nào.

Answer 3

Bạn cũng có thể in ra các giá trị của high và low. Sẽ dễ dàng hơn nhiều khi theo dõi đệ quy.

Answer 4

Chỉ cần làm theo việc thực hiện ...

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 

có thể tiếp tục nhưng đó là nơi mà các chuỗi bạn không mong muốn được thực thi.

Answer 5

Sau 4 dòng sản lượng thấp = 0, trung = 0, cao = 1 để gọi mergesort (giữa + 1, cao) sẽ không in gì (1 < 1 là false)

Answer 6

Các thụt đầu dòng trong tương ứng sau để đệ quy:

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

Answer 7

Chạy đoạn mã này để hiểu rõ đệ quy. Tôi đã xem xét độ sâu ngăn xếp trong bảng điều khiển.Hy vọng nó dễ hiểu!

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

Answer 8

Hợp nhất sắp xếp sử dụng thuật toán đệ quy để tạo cây nhị phân hoàn chỉnh với chiều cao của log N, là N số nút của cây đó (đây là lý do hiệu quả). Trong hình ảnh tiếp theo, bạn có thể thấy từng bước lưu lượng của thuật toán này cho trường hợp của bạn, với cây nhị phân được tạo (mà tôi nghĩ là cách tốt nhất để hiểu cách nó hoạt động):

Binary tree that is generated using Merge Sort with an array of 8 positions

Phân loại hợp nhất làm là chia mảng thành hai phần đệ quy, đi đầu tiên đến nửa thấp nhất cho đến khi chúng tôi đạt đến một phần tử đơn nhất, rồi chia nhỏ phần cao hơn từ phần tử thấp nhất gần đây nhất. Đây là lý do tại sao nó gọi chính nó hai lần cho mỗi cuộc gọi trước đó, để tạo ra một cây nhị phân hoàn chỉnh dừng khi chúng ta đạt đến một đơn vị (với các nút lá) và chỉ hợp nhất khi chúng ta có hai (với các nút cha). Trong hình dưới đây bạn có thể thấy mảng của bạn được chia một cách đệ quy, từng bước:

Step by step division of an array of 8 elements using Merge Sort

Answer 9

Đến eclipse công cụ gỡ lỗi.Thực hiện theo các bước và bạn sẽ tìm thấy quy tắc đệ quy kép. Đó là những gì tôi làm.