www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Making sense of recursion

reply zbr <adnansignsup gmail.com> writes:
Hi, this question is not specifically D related but I'll just ask 
anyway. Consider the following snippet:

void mergeSort(int[] arr, int l, int r)
{
    if (l < r)                       // 1
    {
       int m = l+(r-l)/2;            // 2
       mergeSort(arr, l, m);         // 3
       mergeSort(arr, m+1, r);       // 4
       merge(arr, l, m, r);          // 5
    }                                // 6
}                                   // 7

mergeSort(arr, 0, 4);

When I see this, I visualize the recursion to perform this way:

mergeSort(arr, 0, 4):
     0 < 4 ? true: mergeSort(0, 2):
         0 < 2 ? true: mergeSort(0, 1):
             0 < 1 ? true: mergeSort(0, 0):
                 0 < 0 ? false: //reach the end of mergeSort / 
reach line 6 and then 7

I don't see the computer ever reaching line 4 and 5? Obviously 
I'm wrong but where is my mistake?

Thanks.
Jun 25 2018
next sibling parent ag0aep6g <anonymous example.com> writes:
On 06/25/2018 07:45 PM, zbr wrote:


 void mergeSort(int[] arr, int l, int r)
 {
     if (l < r)                       // 1
     {
        int m = l+(r-l)/2;            // 2
        mergeSort(arr, l, m);         // 3
        mergeSort(arr, m+1, r);       // 4
        merge(arr, l, m, r);          // 5
     }                                // 6
 }                                   // 7
 
 mergeSort(arr, 0, 4);
 
 When I see this, I visualize the recursion to perform this way:
 
 mergeSort(arr, 0, 4):
      0 < 4 ? true: mergeSort(0, 2):
          0 < 2 ? true: mergeSort(0, 1):
              0 < 1 ? true: mergeSort(0, 0):
                  0 < 0 ? false: //reach the end of mergeSort /
reach 
 line 6 and then 7
 
 I don't see the computer ever reaching line 4 and 5? Obviously I'm wrong 
 but where is my mistake?


You seem to think that a recursive call takes over completely, and that 
the caller ceases to exist. That's not so. mergeSort does call "itself", 
but that means there's two active calls now. And when it calls "itself" 
again, there's three. And so on. When an inner call returns, the outer 
one resumes with the next line as usual.

It's not just a list of recursive calls, it's a tree:

mergeSort(0, 3)
     mergeSort(0, 1) // line 3
         mergeSort(0, 0) // line 3
         mergeSort(1, 1) // line 4
         merge // line 5
     mergeSort(2, 3) // line 4
         mergesort(2, 2) // line 3
         mergesort(3, 3) // line 4
         merge // line 5
     merge // line 5
Jun 25 2018
prev sibling next sibling parent Colin <grogan.colin gmail.com> writes:
On Monday, 25 June 2018 at 17:45:01 UTC, zbr wrote:

 Hi, this question is not specifically D related but I'll just 
 ask anyway. Consider the following snippet:

 [...]


Your mistake is in your visualization :-)

But... more like:

0 < 4 ? true : mergeSort(0,2) && mergeSort(3, 4)
And so on.

I.e, the it's not either or to run the second mergeSort, they 
both happen.
Jun 25 2018
prev sibling parent Timoses <timosesu gmail.com> writes:
On Monday, 25 June 2018 at 17:45:01 UTC, zbr wrote:

 Hi, this question is not specifically D related but I'll just 
 ask anyway. Consider the following snippet:

 void mergeSort(int[] arr, int l, int r)
 {
    if (l < r)                       // 1
    {
       int m = l+(r-l)/2;            // 2
       mergeSort(arr, l, m);         // 3
       mergeSort(arr, m+1, r);       // 4
       merge(arr, l, m, r);          // 5
    }                                // 6
 }                                   // 7

 mergeSort(arr, 0, 4);

 When I see this, I visualize the recursion to perform this way:

 mergeSort(arr, 0, 4):
     0 < 4 ? true: mergeSort(0, 2):
         0 < 2 ? true: mergeSort(0, 1):
             0 < 1 ? true: mergeSort(0, 0):
                 0 < 0 ? false: //reach the end of mergeSort / 
 reach line 6 and then 7

 I don't see the computer ever reaching line 4 and 5? Obviously 
 I'm wrong but where is my mistake?

 Thanks.


It's a stack (https://en.wikipedia.org/wiki/Call_stack).

When the program calls a function it is pushed onto the stack. If 
that function returns it pops from the stack and the previous 
function gets to continue execution from where it stopped before.
Jun 26 2018