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

I'm not sure if I'll be able to explain it very well, but I'll explain it using fibonacci instead. A recursive way for calculating fibonacci numbers are:

public static int getFib(int n) {
    if(n <= 2) return 1;
    return getFib(n-1)+getFib(n-2);
}

What actually happens in the code is that it will obviously go down the method calls until it gets a first return. So getFib(n-1) will keep getting called until n <= 2 then it will go back up the method stack and since it now has a value for that getFib(n-1) it will call the getFib(n-2). So say our initial call is with 4, what happens is:

getFib(4) //Initial call
  getFib(4-1=3) //Left hand recursive call level 1
    getFib(3-1=2) //Left hand recursive call level 2
      return 1 //This would be level 3
    getFib(3-2=1) //Right hand recursive call level 2
      return 1 //level 3
  getFib(4-2=2) //Right hand recursive call level 1
    return 1

Not sure if that makes any sense, this image might visualise it a bit:
_{(source: fortystones.com)}

The above code would basically make a depth first (taking the left children first) traversal through that tree.

Answer 2

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