Making sense of recursion

zbr adnansignsup at gmail.com
Mon Jun 25 17:45:01 UTC 2018


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.


More information about the Digitalmars-d-learn mailing list