is this compiler optimization in context of recursion?

Question

I was writing factorial using tail recursion and I have a question here. My original function looks like this

Code snippet A

#include <stdio.h>

int main(void)
{
 int n = 0;

 printf("Enter number to find factorial of : ");
 scanf("%d",&n);

 printf("fact == %d\n",fun(n,1));

 return 0;
}

int fun(int n, int sofar)
{
 int ret = 0;

 if(n == 0)
  return sofar;

 ret = fun(n-1,sofar*n);

 return ret;
}

However, even if I do not use return, it still works. This does not make perfect sense since I am returning the value only in the base case. Say if n==5, then 120 would be returned at the base case. But what gets returned from 4th invocation back to the 3rd invocation cannot be predicted since we are not explicitly specifying any return unlike in Code snippet A.

Code snippet B

int fun(int n, int sofar)
{
 int ret = 0;

 if(n == 0)
  return sofar;

 ret = fun(n-1,sofar*n);
}

I am thinking the above works because of some kind of compiler optimization ? Because If I add a printf statement to Code snippet B, it does not work anymore.

Code snippet C

 int fun(int n, int sofar)
    {
     int ret = 0;

     if(n == 0)
      return sofar;

     ret = fun(n-1,sofar*n);

     printf("now it should not work\n");
    }

Probably the printf causes something to be removed from the stack? Please help me understand this.

@deviantfan Considering that UB is very common in production code (I've heard estimates that over 90% of the programs out there contain UB), I would like to argue that people should bother understanding UB, It's quite critical to understand it to know how to avoid it and fix it. — Art, Jul 02 '15 at 16:50
@Art Understanding what´s wrong / how to fix it and understanding why exactly something strange happens in a UB situation is a big difference... — deviantfan, Jul 02 '15 at 17:11
the posted code, when compiling, raises a critical warning that the prototype for 'fun()' is missing. Suggest placing that prototype just before the main() function. — user3629249, Jul 02 '15 at 17:40

score 3 · Answer 1 · edited May 23 '17 at 12:29

3

Not returning a value from a fuction which should return a value is undefined behavior.

If it works by any luck then it's not an optimization but just a coincidence given by how and where these automatic allocated values are stored.

edited May 23 '17 at 12:29

Community

1
1

answered Jul 02 '15 at 16:22

Jack

131,802
30
241
343

score 2 · Answer 2 · answered Jul 02 '15 at 16:23

One could speculate about the reason why this works, but there is no way to give a definitive answer: reaching the end of a value-returning function without the return statement and using the return value is undefined behavior, with or without optimization.

The reason this "works" in your compiler is that the return mechanism used by your compiler happens to have the right value at the time the end of function is reached. For example, if your compiler returns integers in the same register that has been used for the last computation in your code (i.e. ret = fun(n-1,sofar*n)) then the right value would be loaded into the return register by accident, masking undefined behavior.

score 1 · Answer 3 · answered Jul 02 '15 at 16:25

It works because the return value is almost always stored in a specific CPU register (eax for x86). This means that is you don't explicitly return a value, the return register will not be explicitly set. Because of that, its value can be anything, but it is often the return value of the last called function. Thus, ending a function with myfunc() is almost guaranteed to have the same behavior as return myfunc(); (but it's still undefined behavior).

score 1 · Answer 4 · answered Jul 02 '15 at 17:55

Here is the reason 'something' is calculated.

the call to printf() has a returned value (very rarely used) of the number of characters printed (including tabs, newlines, etc)

in the 'C' code snippet, printf() is returning 23.

'int' returned values are always returned in the same register.

The printf() set that register to 23.

So, something is returned, nothing was removed from the stack.

score 0 · Answer 5 · answered Jul 02 '15 at 16:48

The reason why it seems to work in B is because the return value is most likely passed in a register on your architecture. So returning through all the layers of recursion (or if the compiler optimized the whole thing into iteration) nothing touches that register and your code appears to work.

A different compiler might not allow this to happen or maybe the next version of your compiler will optimize this differently. In fact, the compiler can remove most of the function because it is allowed to assume that since undefined behavior can't happen it must mean that the part of the function where the undefined behavior seems to happen will never be reached and can be safely removed.

is this compiler optimization in context of recursion?

5 Answers5