CODEWITHSUNDEEP
c++c
Gautam Kumar
Gautam Kumar

Reputation: 1170

multiple recursion

I have a doubt that ,inside a block if the same function is called two or more than two times recursively,then what is the order of execution?

e.g.:in case of mergesort ,for partition if i do like this 

mergesort(int a[], int low, int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
mergesort(a,low,mid);
mergesort(a,mid+1,high);
merge(a,low,high,mid);
}

then (1) will mergesort(a,low,mid), mergesort(a,mid+1,high) and merge(a,high,mid) be called one by one if condition (low

(2) Or will the call to merge(a,low,mid) will go on recursively and then after merge(a,mid+1,high) is executed recursively and at last merge(a,low,mid) is executed .

I know this is very simple for you skilled guys,but please do a favour to me by answering this.

Upvotes: 0

Views: 4131

Answers (5)

uzumaki
uzumaki

Reputation: 124

Here's an extension of @phoxis's answer showing the call stack (as he mentioned it in his answer). I think understanding the call stack is how you can make sense of the tree:

enter image description here

Upvotes: 0

phoxis
phoxis

Reputation: 61910

                        merge_main_call_0
                              |
                              |
              +-----------------+------------------+
              |                                    |
              +                                    +
       merge_1_call_1                         merge_2_call_4
              +                                    +
              |                                    |
    +---------+---------+                +---------+---------+
    |                   |                |                   |
    +                   +                +                   +
 merge_1_call_2   merge_2_call_3     merge_1_call_5    merge_2_call_6
 (here `if' is false)                     (here `if' is false)

This shows the call tree. The first function will be called first whenever the if is true at some level or recursion. When the if is false in some level or recursion, it will go back to the last function call (the one from which it was called), which will start the execution after the first function call, which will call the second function. The second function then repeats the same thing.

In the above diagram merge_1_call_n means that the merger function 1 is called the nth time.

When the first time the if condition of will become false in some recursive level it will return back to the last recursive level and start executing from where it left from, which will then call the second function. Similarly, recursively when at this level this function call will return, it will execute the merge function, and then the control returns from this level to the last recursive level.

It is very important to understand what a recursion level is. To do this draw the first function call as the left most child of a n-ary tree and the last call as the rightmost child, and try to form a tree like structure. The depth first search (pre-order) will result in the call sequence of the functions.

UPDATE

For the recursive call process going on, check out the Call Stack and Activation Records

Upvotes: 6

Vineet G
Vineet G

Reputation: 195

In main merge function if if condition is true then first merge() is called. Compiler saves everything on stack and call main merge again. It keeps repeating this until if condition is false. As soon as if condition is false compiler retreat back by popping from stack. It will keep popping from stack until it comes back to the very first merge() saved on stack. After popping and calling this merge it will go on to second merge and will repeat the whole process. Similary with the last merge.

So the Order is: First Merge, then keep repeating until if fails, second merge, keep repeating..., third merge

Upvotes: -1

Ignacio Vazquez-Abrams
Ignacio Vazquez-Abrams

Reputation: 798606

Two function calls means that the function will be called two times, if the condition is true.

Upvotes: 0

Greg Hewgill
Greg Hewgill

Reputation: 993015

In your example, if low < high, then the mergesort() function will be called twice and the merge() function once. However, because this function is recursive, calls to mergesort() might call itself more times (depending on the values passed to it).

Upvotes: 1

Related Questions