Find maximum value in an array by recursion
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:
Example:
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
Justin Bains
Updated on September 18, 2020Comments
-
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 over 11 years@JustinBains
left
andright
are the indexes of the first and last element of the arrays(Initial as well as intermediate arrays). -
SomeWittyUsername over 11 yearsA 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 over 7 yearsWelcome 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.