Making sense of recursion

[ag0aep6g]

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