Making sense of recursion

Timoses timosesu at gmail.com
Tue Jun 26 07:49:01 UTC 2018


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.


More information about the Digitalmars-d-learn mailing list