Divide and Conquer Recursion

Question

I am just trying to understand how the recursion works in this example, and would appreciate it if somebody could break this down for me. I have the following algorithm which basically returns the maximum element in an array:

int MaximumElement(int array[], int index, int n)
    {  
        int maxval1, maxval2; 
        if ( n==1 ) return array[index];
        maxval1 = MaximumElement(array, index, n/2); 
        maxval2 = MaximumElement(array, index+(n/2), n-(n/2));
        if (maxval1 > maxval2)
            return maxval1;
        else
            return maxval2;
    }

I am not able to understand how the recursive calls work here. Does the first recursive call always get executed when the second call is being made? I really appreciate it if someone could please explain this to me. Many thanks!

Answer 1

Code comments embedded:

    // the names index and n are misleading, it would be better if we named it:
    // startIndex and rangeToCheck
int MaximumElement(int array[], int startIndex, int rangeToCheck)
{  
    int maxval1, maxval2; 

    // when the range to check is only one cell - return it as the maximum
    // that's the base-case of the recursion
    if ( rangeToCheck==1 ) return array[startIndex];
    // "divide" by checking the range between the index and the first "half" of the range
    System.out.println("index = "+startIndex+"; rangeToCheck/2 = " + rangeToCheck/2);
    maxval1 = MaximumElement(array, startIndex, rangeToCheck/2);
    // check the second "half" of the range
    System.out.println("index = "+startIndex+"; rangeToCheck-(rangeToCheck/2 = " + (rangeToCheck-(rangeToCheck/2)));
    maxval2 = MaximumElement(array, startIndex+(rangeToCheck/2), rangeToCheck-(rangeToCheck/2));

    // and now "Conquer" - compare the 2 "local maximums" that we got from the last step
    // and return the bigger one
    if (maxval1 > maxval2)
        return maxval1;
    else
        return maxval2;
 }

Example of usage:

int[] arr = {5,3,4,8,7,2};
int big = MaximumElement(arr,0,arr.length-1);
System.out.println("big = " + big);

OUTPUT:

index = 0; rangeToCheck/2 = 2
index = 0; rangeToCheck/2 = 1
index = 0; rangeToCheck-(rangeToCheck/2 = 1
index = 0; rangeToCheck-(rangeToCheck/2 = 3
index = 2; rangeToCheck/2 = 1
index = 2; rangeToCheck-(rangeToCheck/2 = 2
index = 3; rangeToCheck/2 = 1
index = 3; rangeToCheck-(rangeToCheck/2 = 1
big = 8

Answer 2

What is happening here is that both recursive calls are being made, one after another. The first one searches have the array and returns the max, the second searches the other half and returns the max. Then the two maxes are compared and the bigger max is returned.

Answer 3

Yes. What you have guessed is right. Out of the two recursive calls MaximumElement(array, index, n/2) and MaximumElement(array, index+(n/2), n-(n/2)), the first call is repeatedly carried out until the call is made with a single element of the array. Then the two elements are compared and the largest is returned. Then this comparison process is continued until the largest element is returned.