Найти максимальное значение в массиве путем рекурсии

Ответ 1

Вы используете алгоритм Divide и Conquer для нахождения максимального элемента из массива. Сначала вы делите массив на отдельные элементы (делим), затем вы сравниваете элементы (побеждаете). Вы делите массив с помощью рекурсивного вызова findMaxHelper.

Общая идея "разделяй и властвуй" показана на рисунке:

Пример:

Здесь max совпадает с вашей findMaxHelper функцией с двумя аргументами, то есть left и right.

Посмотрите этот пример для более глубокого понимания концепции.

Ответ 2

Jaguar положил концепцию довольно хорошо, и Пол дал правильное и подробное объяснение. Чтобы добавить к этому, я хотел бы поделиться простым C-кодом, который дает вам представление о том, как код получает казнены. Здесь используется код с тем же входным Jaguar:

#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 может скопировать вставку кода на машину ur 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 

Ответ 3

findMaxHelper делит массив на половину каждый раз и находит max слева, справа:

Например, у вас есть массив 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

Ответ 4

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

Ответ 5

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

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

          }