Understanding double recursion

Question

I'm able to comprehend recursion easily if there is just one recursive call within a function. However, I am really getting confused when I see two or more recursive calls within the same function. Example:

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 understand one thing that n gets decremented by half during each recursive call. I just don't understand how the next recursive call works. It gets confusing and my understanding until that point falls apart and I give up. I would be really thankful if somebody could please illustrate this manually with a neat example. I already did the programming, and printed the outputs. However, I don't understand how the calculations behind this work. Here is my understanding until the point where everything gets to nothing:

int a[] = {1,2,10,15,16,4,8}

Initial call: MaximumElement(a, 0, 7)

The function begins: First call: MaximumElement(a, 0, 7/2) n now becomes 7/2 = 3

Second Call: MaximumElement(2,0,3/2) n now becomes 3/2 = 1

The base condition is met and the max1 gets a[0] = 1

Here is where all hell breaks loose: The second recursive call begins with index 0 and n = index + n/2 = 0 + 1/2 = 0? When I print the values the program shows 3 as the value for n when the second call is being made.

I have programmed extensively, but I am really having a nightmare with this. Many thanks to somebody that can break this down for me!!

That was the pseudocode above, but see below for the java code I wrote (it might make it easier for you if you are trying to run it):

        public int MAXIMUMELEMENT(int a[], int i, int n)
        {
        int max1, max2;

        System.out.println("1: " + i + " 2: " + n);

        if(n == 1)
        {
            System.out.println("Returning " + a[i]);
        return a[i];
        }



        max1 = MAXIMUMELEMENT(a, i, n/2);

        System.out.println("Index: "+i+" "+" Variable: "+max1+" n value: "+n);


            max2 = MAXIMUMELEMENT(a, i + (n/2), n - (n/2));

        System.out.println("Index2: " + i + " " + "Variable2: " + max2);


        if(max1 > max2)
        {
            System.out.println("Returning.... " + max1 );    
                return max1;
        }
        else
        {
        System.out.println("Returning.... " + max2);     
        return max2;
        }
}

Answer 1

It sounds like you already understand the base case and know how recursion works, so the key to understanding your particular example is to note that given the initial array

a = [1,2,10,15,16,4,8]

you are, at the "top level" computing two things:

maxval1 = MaximumElement(array, 0, 3); 
maxval2 = MaximumElement(array, 3, 4);

which says

• make maxval1 the maximum value from the array in the range starting from index 0 of size 3
• make maxval2 the maximum value from the array in the range from index 3 of size 4

So

• maxval1 will indeed be 10
• maxval2 will indeed be 16

and your answer will be 16.

The nice thing about recursion is that you don't have to worry about tracing things too extensively. If you trust your base case and the manner in which you get to your base case, then understanding one level should suffice.

I think you got stuck where you said "all hell breaks loose" because the second recursive call begins with a starting index of 0. It doesn't. It starts at index 3. (That is, assuming your second recursive call is the one computing maxVal2).

Here is a bit of an abbreviated trace of how your computation works out. I've taken the liberty to rename your function to m and to assume that maxVal1 and maxVal2 were computed a little more "functionally".

a = [1,2,10,15,16,4,8]

m(a, 0, 7)
= m(m(a, 0, 3), m(a, 3, 4))
= m(m(m(a, 0, 1), m(a, 1, 2)), m(a, 3, 4))
= m(m(a[0], m(a, 1, 2)), m(a, 3, 4))
= m(m(1, m(a, 1, 2)), m(a, 3, 4))
= m(m(1, m(m(a, 1, 1), m(a, 2, 1)), m(a, 3, 4))
= m(m(1, m(a[1], a[2])), m(a, 3, 4))
= m(m(1, m(2, 10)), m(a, 3, 4))
= m(m(1, 10), m(a, 3, 4))
= m(10, m(a, 3, 4))
= …
= 16