Recursion problem

This is a discussion on Recursion problem within the C Programming forums, part of the General Programming Boards category; 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[], ...

  1. #1
    Registered User
    Join Date
    Dec 2005
    Posts
    25

    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?

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    When low and mid are both zero, they enter that function, which immediately returns because low is not less than high.


    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    Registered User
    Join Date
    Dec 2005
    Posts
    25
    ok , if that happens "c" and "d" won't be executed as the block following if will be skipped.

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Template Recursion Pickle
    By SevenThunders in forum C++ Programming
    Replies: 20
    Last Post: 02-05-2009, 08:45 PM
  2. Recursion problem
    By trnd in forum C Programming
    Replies: 2
    Last Post: 02-01-2009, 02:06 PM
  3. Problem of understanding recursion
    By ixing in forum C Programming
    Replies: 2
    Last Post: 05-02-2004, 03:52 PM
  4. half ADT (nested struct) problem...
    By CyC|OpS in forum C Programming
    Replies: 1
    Last Post: 10-26-2002, 08:37 AM
  5. recursion problem
    By dustinc in forum C++ Programming
    Replies: 1
    Last Post: 10-29-2001, 03:29 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21