0

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.

Gautam Kumar
  • 1,162
  • 3
  • 14
  • 29

5 Answers5

6
                        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

phoxis
  • 60,131
  • 14
  • 81
  • 117
1

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).

Greg Hewgill
  • 951,095
  • 183
  • 1,149
  • 1,285
  • :Thanks.Can you please tell me in which order will the functions be called?And how will they be executed?I am having misconception with recursion.It will be really very kind if you clear my doubt with help of stack mechanism or any other mechanism of implementation of recursion.Or if you can please give me the link to clear my doubts on recursion. – Gautam Kumar Sep 26 '11 at 04:50
  • @gautamkumar: check this link: http://stackoverflow.com/questions/5631447/how-recursion-works-in-c – Aamir Sep 26 '11 at 05:13
  • @aamir:can you please tell what are the things i.e. argment,return value etc that are pushed in stack?Please explain. – Gautam Kumar Sep 26 '11 at 05:32
  • @gautam kumar: they are not practically pushed, a new stack frame is created, by manipulating the base pointer register and the stack pointer register,which points to the new stack frame. You should have a look at function activation records: http://enel.ucalgary.ca/People/Norman/engg335_fall1998/activ_rec/ – phoxis Sep 26 '11 at 06:14
  • @phoxis:Please answer last part of the question i.e. "when the if condition is true then all the three functions will be called one by one or the call to first function i.e. mergesort(a,low,mid) will be called repeatedly.please clear my doubt." – Gautam Kumar Sep 26 '11 at 06:21
  • one by one,normally.But when the first function is called, but as it is calling the same function (itself) with new values, a new stack frame is called and this function code is re-executed,in which case again only the first function is called.When the function calls will return from the deeper recursion depth to a certain depth, then the second function will be called.Look at the diagram in my answer.Note the function number and the order when it is called.Trace manually.Here in this context the "repeatedly" does not have iterative effect, because the functions are called in different depths. – phoxis Sep 26 '11 at 06:35
0

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

uzumaki
  • 124
  • 1
  • 4
0

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

Ignacio Vazquez-Abrams
  • 776,304
  • 153
  • 1,341
  • 1,358
  • :Thanks.Can you please tell me in which order will the functions be called?And how will they be executed?I am having misconception with recursion.It will be really very kind if you clear my doubt with help of stack mechanism or any other mechanism of implementation of recursion.Or if you can please give me the link to clear my doubts on recursion. – Gautam Kumar Sep 26 '11 at 04:51
  • The first will be called first. The second will be called second. Any other calls happen in a separate stack frame. – Ignacio Vazquez-Abrams Sep 26 '11 at 05:05
-1

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

Vineet G
  • 175
  • 1
  • 1
  • 8