遞歸如何工作

Question

static void sort(int array[]) 
{ 
    //int array[]={20,40,30,60,70,80,50,90}; 
    if(array.length==1) 
     return; 

    int mid=array.length/2; 
    int part1[]=new int[mid]; 
    int part2[]=new int[array.length-mid]; 

    for(int i=0; i<array.length; i++) 
    { 
     if(i<mid) 
     { 
      part1[i]=array[i]; 
     } 
     else 
     { 
      part2[i-mid]=array[i]; 
     } 
    } 

    sort(part1); 
    sort(part2); 

    merge(part1,part2,array); 
    //for(int x=0; x<part1.length; x++) 
     //System.out.print(part1[x]+" "); 

    //for(int x=0; x<part2.length; x++) 
     //System.out.print(part2[x]+" "); 

} 

我知道遞歸是稱爲自我的方法（函數）。 （part1）方法，然後sort（part1）被反覆執行，以及sort（part2）和merge（part1，part2）如何執行並調用自身的sort（part1）方法，數組）被執行，爲什麼這個代碼不是無限的，程序是如何停止的。在Java中 抱歉即時通訊新

Answer 1

每次遞歸調用工作段上的一半大父通話：

int mid=array.length/2; 

當子段長度達到一個，遞歸處於「基本情況」並且該方法返回：

if(array.length==1) 
    return; 

我覺得這其實是Quicksort的實現。該算法屬於一系列算法，稱爲Divide and Conquer，因爲它們通過遞歸地將問題分成越來越小的部分，解決較小的問題，並最終組合較小的解決方案以獲得全部結果。

現在您已經知道算法的調用方式了，如果您想更好地瞭解它的工作原理，我建議您更詳細地研究該算法。維基百科的文章甚至有一個很好的動畫來幫助你想象算法的工作原理。

---

注意，代碼張貼將結果爲空數組無限遞歸。 Quicksort避免這種情況的通常方法是使用長度≤1而不是長度= 1檢查基本情況。

Answer 2

它停止，因爲part1和part2是較小的數組比原來的一個。最後他們只是一個元素的陣列，所以

if(array.length==1) 
    return; 

火災。一般而言，這裏有一個經常性函數，形式如下：

T(n)  = T(n/2)  + T(n/2)  + O(n) 
    ----   ------   ------   --- 
sort(part)  sort(part1)  sort(part2)  merge 

T(1) = 1 # 

Answer 3

在每次遞歸調用中，將數組分成2個新的半長陣列。你的基本條件說，如果數組的大小是1，然後返回。這就是程序停止的地方，因爲數組的大小最終爲1。

Answer 4

每次調用sort方法時，都會將當前方法調用保持在堆棧中，並將新調用推送到sort。因此，在該方法調用結束時，之前的排序調用會被執行，並且這種情況會持續到堆棧爲空，或者返回sort的第一個調用。

https://softwareengineering.stackexchange.com/questions/25052/in-plain-english-what-is-recursion

上面的例子解釋了很詳細的遞歸。