Find maximum value in an array by recursion

21,571

Solution 1

You are using Divide and Conquer algorithm for finding the maximum element from the array. First, you are dividing the array into individual elements (divide), then you are comparing the elements (conquer). You are dividing the array using calling findMaxHelper recursively.

The general idea of Divide and conquer is shown in the figure:

enter image description here

Example:

enter image description here Here max is same as your findMaxHelper function with two arguments i.e. left and right.

Check this example for more in depth understanding of the concept.

Solution 2

Jaguar has put the concept quite nicely and Paul has provided correct and detailed explanation. To add to this , I would like to share a simple C code that gives you an idea how the code gets executed. Here's the code with the same input Jaguar used :

#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 can copy paste the code on ur linux machine ...Maybe put sleep(5) after every printf and see how recursion ACTUALLY works !... Hope this helps... I will also share the output from my system here :

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 
Share:
21,571
Justin Bains
Author by

Justin Bains

Updated on September 18, 2020

Comments

  • Justin Bains
    Justin Bains over 3 years
    // 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
    

    I am having a hard time understanding what is happening in this pseudo-code.

    Can someone help explain what is happening at each line. I need to understand this code before I can answer the questions.

    I know that the function findMax calls the helper function findMaxHelper, then findMaxHelper uses recursion. Other than that, I really don't understand it.

  • Jainendra
    Jainendra over 11 years
    @JustinBains left and right are the indexes of the first and last element of the arrays(Initial as well as intermediate arrays).
  • SomeWittyUsername
    SomeWittyUsername over 11 years
    A general suggestion to anyone struggling with understanding recursive code: do not try to dive deep and follow. Better do a "zoom out" and try to understand the bigger picture. Recursive functions usually take the input, perform basic operation and repeat the same for a smaller problem, just like in this code snippet. You should try to identify the smaller problem(s), that's the core of understanding such code.
  • sprinter
    sprinter over 7 years
    Welcome to SO. Note that the OP was really asking for an explanation of the psuedo-code. Including an answer that is code with no explanation is unlikely to be useful.