Understanding double recursion

问题:

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;
        }
}

回答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

回答2:

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: Recursive fibonacci tree http://www.fortystones.com/wp-content/uploads/2011/08/fibonacci-recursion-tree.png

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

回答3:

It seems to me that you have confused about the running order of the recursive calls. Keep in mind that, second call (maxval2) does not get called until the first call (maxval1) finishes. maxval1 call itself has two more recursive calls within itself and so on. So without all these inner recursive calls being finished, the program does not reach the maxval2 line.

Try debugging instead of running the code (in Eclipse for e.g.) and move step by step to see how it actually goes about each recursive call.