CODEWITHSUNDEEP
javaalgorithmsortingrecursion
King Doge
King Doge

Reputation: 21

recursion in mergesort: two recursive calls

private void mergesort(int low, int high) {     //line 1
if (low < high) {                               //line 2
    int middle = (low + high)/2 ;               //line 3
    mergesort(low, middle);                     //line 4
    mergesort(middle+1, high);                  //line 5
    merge(low, middle, high);                   //line 6
}}                                              //line 7

I understand the fact that when the if statement is false you exit the method/function. For example, if i call mergesort(0, 5) in the main method the first mergesort(low, middle) will run 3 times and terminate, then the program will go to line 7.

What i am confused about is why high suddenly turns from 0 to 1 when the program goes back tomergesort(middle+1, high); in line 5.

here is another example of a similar but simpler program

public static void recursionExample(int i){      //line 1
    if(i < 3){                                   //line 2
        recursionExample(i+1);                   //line 3
        recursionExample(i-1);                   //line 4
    }                                            //line 5 
}                                                //line 6

this time if i call recursionExample(0) line 3's recursion(i+1); will run 3 times until the if statement is false, then it will go to line 6, then after that the program will go to line 4 recursion(i-1); However, i suddenly turns from 3 to 2, when it goes from line 6 to line 4. This is what i find most confusing. Why does i turns into 2 when the second recursive method is called.

Upvotes: 0

Views: 93

Answers (2)

Ga&#235;l J
Ga&#235;l J

Reputation: 15050

Considering your second snippet, the order of calls is the following (represented as a tree for ease of understanding) :

- recursionExample(0)
  - recursionExample(1)
    - recursionExample(2)
      - recursionExample(3), here no more recursion
      - recursionExample(1)
        ...
    - recursionExample(0)
      ...
  - recursionExample(-1)
    - recursionExample(0)
      ...
    - recursionExample(-2)
      ...

Upvotes: 0

Eran
Eran

Reputation: 393781

Regarding your second snippet :

public static void recursionExample(int i){     
    if(i < 3){                                 
        recursionExample(i+1);  // this is called for the last time when i==2, i.e. the
                                // last call is recursionExample(3). When that call 
                                // returns, i is still equal 2, since calling  
                                // recursionExample(i+1) doesn't change the value of the
                                // local variable i of the current method call

        recursionExample(i-1);  // Therefore when this line is first called, i is equal 2
    }                                         
}

Upvotes: 1

Related Questions