# Recursion problem

• 11-13-2006
ramayana
Recursion problem
Given below is a function which is part of a bigger program implementing Merge Sort http://linux.wku.edu/~lamonml/algor/sort/merge.html
Code:

``` void merge_sort(int a[], int low , int high) //a  {   int mid;   if(low<high)     {     mid=(low+high)/2;     merge_Sort(a,low,mid)//b;     merge_Sort(a,mid+1,high);//c     simple_merge(a,low,mid,high); //d     } }```
Now I cant figure out the way this recursion is working . According to me there would be infinite number of calls made between "a " and "b" .

Let us take array 5,8,10 we pass at first merge_sort(a,0,2). mid becomes 1 so b calls a with low=0 and high = 1. Next mid becomes 0 and b calls a with low=0 and high =0 . This time low=high and the "if condition" is false , mid will be 0 and will continue to be 0 and hence "b" will go on calling "a" . But the program actually works perfectly , so where am I wrong in my tracing of the program?
• 11-13-2006
quzah
When low and mid are both zero, they enter that function, which immediately returns because low is not less than high.

Quzah.
• 11-13-2006
ramayana
ok , if that happens "c" and "d" won't be executed as the block following if will be skipped.
• 11-13-2006
quzah
No, they'll still execute also, but in all of those instances "less" isn't, so they each in turn return. Consider:
Code:

```if( low{0} < high{1} ) {     mid = high / 2 {0};     fun( a, {0}, {0} ) -> gets to "if 0 < 0" ... so that one returns (this is b)     fun( a, {1}, {0} ) -> gets to "if 1 < 0" ... so that one returns (this is c)     sim( a, {0}, {0}, {1} ) -> is d, whatever that is...```
Everything here ins {} is just an illustration of the value being passed, not actual intended code.

Quzah.