通過遞歸找到數組中的最大值

Question

// Find a maximum element in the array. 
findMax(A) 
    findMaxHelper(A, 0, A.length) 

findMaxHelper(A, left, right) 
    if (left == right - 1) 
     return A[left] 
    else 
     max1 = findMaxHelper(A, left, (right + left)/2) 
     max2 = findMaxHelper(A, (right + left)/2, right) 

     if (max1 > max2) 
     return max1 
     else 
     return max2 

我很難理解這個僞代碼中發生了什麼。

有人可以幫助解釋每一行發生了什麼。在回答問題之前，我需要了解這些代碼。

我知道函數findMax調用助手函數findMaxHelper，然後findMaxHelper使用遞歸。除此之外，我真的不明白這一點。

Answer 1

您正在使用Divide and Conquer算法來查找數組中的最大元素。首先你將數組分割成單獨的元素（除法），然後比較元素（征服）。您正在遞歸調用findMaxHelper來劃分數組。

分而治之的總體思路如圖所示：

例子：

這裏max是一樣的findMaxHelper函數有兩個參數，即left和right。

查看this更深入瞭解該概念的示例。

Answer 2

findMaxHelper陣列分成各佔一半時間，並找到離開的最大，右：

如您有陣A = [1, 3, 5, 8]，叫findMax(A) - >findMaxHelper(A, 0, A.length)：

 max1 | max2 
    1 3 | 5 8 

max1|max2 | max1|max2 
1 |3 | 5 |8 

Answer 3

捷豹已經把概念很好，保羅提供了正確和詳細的解釋。 要添加到此，我想分享一個簡單的C代碼，讓您知道代碼如何執行 。以下是捷豹採用相同的輸入代碼：

#include<stdio.h> 
int findMaxHelper(int A[], int left, int right){ 
    int max1,max2; 
    int static tabcount; 
    int loop; 
    for(loop = 0 ; loop <tabcount;loop++) printf("\t"); 
    tabcount++; 
    printf(" Entering: findMaxHelper(A, left = %d ,right = %d)\n\n",left,right); 
    if (left == right - 1){ 
     for(loop = 0 ; loop <tabcount;loop++) printf("\t"); 
     printf("\b\b\b\b\b\b\bLeaving: findMaxHelper(A, left = %d ,right = %d)| returning %d\n\n",left,right , A[left]); 
     tabcount--; 
     return A[left]; 
    } 
    else 
    { 
     max1 = findMaxHelper(A, left, (right + left)/2); 
     max2 = findMaxHelper(A, (right + left)/2, right); 

     if (max1 > max2){ 
    for(loop = 0 ; loop <tabcount;loop++) printf("\t"); 
    printf("\b\b\b\b\b\b\bLeaving: findMaxHelper(A, left = %d ,right = %d) | returning max1=%d\n\n",left,right,max1); 
    tabcount--; 
    return max1; 
    } 
     else { 
    for(loop = 0 ; loop <tabcount;loop++) printf("\t"); 
    printf("\b\b\b\b\b\b\bLeaving: findMaxHelper(A, left = %d ,right = %d)| returning max2=%d\n\n",left,right,max2); 
    tabcount--; 
    return max2; 
    } 

    } 
} 

int main(){ 
    int A[] = { 34,3,47,91,32,0 }; 
    int Ans =findMaxHelper(A,0,7); 
    printf("And The Answer Is = %d \n",Ans); 
} 

U可以複製粘貼烏爾Linux機器上的代碼......也許把睡眠（5）每個printf的 後，看看如何遞歸實際工作...！ 希望這有助於... 我也會從我這裏系統共享輸出：

Entering: findMaxHelper(A, left = 0 ,right = 7) 

    Entering: findMaxHelper(A, left = 0 ,right = 3) 

     Entering: findMaxHelper(A, left = 0 ,right = 1) 

     Leaving: findMaxHelper(A, left = 0 ,right = 1)| returning 34 

     Entering: findMaxHelper(A, left = 1 ,right = 3) 

      Entering: findMaxHelper(A, left = 1 ,right = 2) 

      Leaving: findMaxHelper(A, left = 1 ,right = 2)| returning 3 

      Entering: findMaxHelper(A, left = 2 ,right = 3) 

      Leaving: findMaxHelper(A, left = 2 ,right = 3)| returning 47 

     Leaving: findMaxHelper(A, left = 1 ,right = 3)| returning max2=47 

    Leaving: findMaxHelper(A, left = 0 ,right = 3)| returning max2=47 

    Entering: findMaxHelper(A, left = 3 ,right = 7) 

     Entering: findMaxHelper(A, left = 3 ,right = 5) 

      Entering: findMaxHelper(A, left = 3 ,right = 4) 

      Leaving: findMaxHelper(A, left = 3 ,right = 4)| returning 91 

      Entering: findMaxHelper(A, left = 4 ,right = 5) 

      Leaving: findMaxHelper(A, left = 4 ,right = 5)| returning 32 

     Leaving: findMaxHelper(A, left = 3 ,right = 5) | returning max1=91 

     Entering: findMaxHelper(A, left = 5 ,right = 7) 

      Entering: findMaxHelper(A, left = 5 ,right = 6) 

      Leaving: findMaxHelper(A, left = 5 ,right = 6)| returning 0 

      Entering: findMaxHelper(A, left = 6 ,right = 7) 

      Leaving: findMaxHelper(A, left = 6 ,right = 7)| returning 0 

     Leaving: findMaxHelper(A, left = 5 ,right = 7)| returning max2=0 

    Leaving: findMaxHelper(A, left = 3 ,right = 7) | returning max1=91 

Leaving: findMaxHelper(A, left = 0 ,right = 7)| returning max2=91 

And The Answer Is = 91 

Answer 4

基本上找到最大數組不推薦用遞歸因爲它不是必需的。 劃分和征服算法（遞歸）花費更多時間。 但即使如果你想使用它，你可以使用我下面的算法。基本上，它帶來陣列的最大元素在第一位置，並有近線性的運行時間（此算法中僅​​僅是一個遞歸幻覺雖然！）：

 int getRecursiveMax(int arr[], int size){ 
      if(size==1){ 
         return arr[0]; 
      }else{ 
       if(arr[0]< arr[size-1]){ 
             arr[0]=arr[size-1]; 
        } 
       return(getRecursiveMax(arr,size-1)); 
      } 

      } 

Answer 5

#include<stdio.h> 
#include<stdlib.h> 

int high,*a,i=0,n,h; 
int max(int *); 

int main() 
{ 

    printf("Size of array: "); 
    scanf("%d",&n); 

    a=(int *)malloc(n*sizeof(int));   //dynamic allocation 
    for(i=0;i<n;i++) 
    { 
     scanf("%d",(a+i)); 
    } 
     i=0; 
    high=*a; 
    h=max(a); 
    printf("The highest element is %d\n",h); 
} 

int max(int *a) 
{ 

    if(i<n) 
    { 
     if(*(a+i)>high) 
     {high=*(a+i);} 
    i++; 
    max(a);      //recursive call 
    } 

    return high; 
}