Thread: recursion and stack - trying to understand

So why not change the code and add some prints

Code:

int fact(int n)
{
    int val;
 
    printf("Called with n=%d\n", n);
    if (n == 1)
        val = 1;
    else
        val = n * fact(n-1);    //b
 
    printf("returning from fact(%d) with result=%d\n", n,val);
    return val;
 
}

The call stack is built by main() calling fact(3) which results in fact(2) being called which results in fact(1) being called. When the inner most call of fact (called as fact(1)) returns, it returns 1. That 1 is multiplied by 2, to return a result of 2 (fact(2)). That value is multiplied by 3, to return a result of 6 (fact(3)). That is the value which gets returned to main(), in the printf() statement, so the value of 5 is returned.

As to what goes on the stack .... whatever is necessary to ensure that sequence of events happens. Generally that will include values of function argument (e.g. main() calling fact(3) will result in a value of 3 on the stack, so it can be retrieved as n inside the fact() function) and tracking call context (so, for example, the deepest call of fact() returns the value of 1 to the call of fact that is calculating fact(2), rather than directly to main()).

The variables and values used by the functions are also usually copied to the stack as well. So, when fact(1) is being executed, there is a val corresponding to it (never used) and and an n (with value 1). However, there is an active call of fact(2) active which called fact(1), and it has its own local version of n and val. Similarly for the call of fact() with argument of 3.

The specifics are highly compiler dependent. Depending on how smart it is, the compiler may eliminate unnecessary variables (it is trivial to rewrite your function so it produces the same result without using the variable val at all, but gives the same result). It may also turn your fact() function into a loop - with no recursion whatsoever - since it is essentially tail-recursive (i.e. the last significant operation it does before returning is call itself, and it is guaranteed that every such call will eventually return). If the compiler does such things, it might eliminate the need for anything on the stack, other than what is needed in main() to call fact(3). And a really smart compiler or linker might even inline the call of fact() completely, and simply print out the value of 6.