Recursion understanding how the method is called

Question

Can someone please explain how the recursion works.I tried to figure out writing down low,mid,high at each recursive call.But I seem to be making a mistake somehow.Can some one please show me the steps.Also I don't understand where the values are returned to in

if(leftmax>rightmax){
    return leftmax;
}
else
    return rightmax;

Here's the code:

public class Maximum{
    public static  int max(int[] a,int low,int high){
        int mid,leftmax,rightmax;
        if(low==high)
            return a[low];
        else{
            mid=(low+high)/2;
            leftmax=max(a,low,mid);
            rightmax=max(a,mid+1,high);
            if(leftmax>rightmax){
                return leftmax;}
            else
                return rightmax;            
        }
    }

    public static void main (String args[]){
        int[] a={32,8,12};
        System.out.println(max(a,0,2));
    }
}

@Jim Garrison: I understand what's going on that other question.But this one I can' t figure out — sam_rox, Jun 05 '14 at 18:36
OK, I've reopened it. I suggest you trace through it with a debugger, step by step. — Jim Garrison, Jun 05 '14 at 19:02

score 1 · Answer 1 · answered Jun 05 '14 at 19:29

So it appears this is the famous Divide and Conquer algorithm for finding an element, in this case, the maximum element.

The method starts with this input:

max(int[] a, int low, int hight)

a[] = { 32, 8, 12 }; //The target array. You want to find the maximum element in it.
low = 0; //The index of the array where you will start searching
high = 2; //The index of the array where you will stop searching

So, basically, low and high defines a "range", you will search the maximum elment within this range, if you want to search the whole array, then you specify the range to be the index 0 and the maximum possible index, that is the length of the array - 1 (Remember, index begins from zero, so you need to substract the offset)

The first condition in the method checks wether you gave a range with one element. In this case, low and high will be the same, becasue they refer to the same index on the array. Therefore, you just return that particular element in the index (You don't have to do any searching, if you are searching the maximum element in a one-element range, then the maximum element is that single element). Returning a[low] or a[high] is the same.

If you gave a range with more than one element, you go into the else section.

Here, you get the middle index of the range.

So, if you specified a range from index 3 (low), to index 7 (high), then the middle index would be 5.
(* (low + high) / 2 *)

You then partition the range into two ranges, the left range and the right range, they both come from the same original range which was splitted by two.

You then perform all the above operations I stated with each of those two ranges, until, at same point, you will split so many ranges, that you will end up with a one-element range, and would return it.

Let's stop here for a second.

Look at the code, we are storing the return values of the splitted ranges in leftmax and rightmax accordingly, but since you are calling the same method, each splitted range will also have it's own leftmax and rightmax and it's own splitted ranges.

It's like you are diving deeper and deeper, the surface being the initial execution of the method.

The last level of deepness is giving a one-element range (result of a previous split). In this case, the method will stop calling itself, because it will actually return a value. Who will catch this returned value? The previous level, which can be very deep also, this deep level will capture the return values of the last level and do the comparition in the code, that is returning the max element, and will return the max element of these two numbers to the level above it, which will do the same, and return it to a higher level, and on and on and on, until you reach the surface level, with the two maximum numbers of each splitted array accordingly, you then check the maximum of these two numbers and return them to you (You are the highest level!).

I hope I explained the whole process clearly and helped you!!

score 0 · Answer 2 · answered Jun 05 '14 at 19:13

1    low=0 high=2 mid=1 
2        low=0 high=1 mid=0
3            low=0 high=0 --> return a[0] --> leftmax == 32
4            low=1 high=1 --> return a[1] --> rightmax == 8
             leftmax > rightmax --> return leftmax == 32
5        low=2 high=2 --> return a[2] --> rightmax == 12
         leftmax > rightmax --> return leftmax == 32

The max() function's job is:

If low and high are equal, return the value pointed to by the index
Otherwise, partition the section of the array we're looking at into two segments and call max() recursively on both halves. Then return the larger of the values returned by the two calls.

I don't understand several stages.Upto step for I understand.Before step 4, low=0,high=0.Then the value 32 is returned to leftmax.Then the line executed is `rightmax=max(a,mid+1,high);`.Since earlier low=high=0,mid=0.Then it would be rightmax=max(a,1,0).Then rightmax=max(a,1,1).This returns a[1]=8 as rightmax. Then since leftmax > rightmax ,leftmax of 32 is returned to WHERE?Is it for leftmax=(a,0,1)?Then how does it move to step 5?In which line does it become low=2 high=2 — sam_rox, Jun 06 '14 at 04:50

Recursion understanding how the method is called

2 Answers2