Infinite recursive calls should raise a stack overflow in this case?

Question

I've recently thought about this case of stack overflow:

int f()  
{  
    return f();  
}  

int main(void)  
{  
    f();  
    return 0;  
}

which definitely crashes the program. But my question is why is this not the same as an infinite loop? The compiler in the case of a recursive call at the return line could realize there's no need to keep any information of the calling function since the returning point to the called function is the same than that of the caller. Now, in this case I agree the compiler needs to keep the information of the functions making the calls in the stack:

int f()
{
    int x = f();
    return x;
}

int main(void)
{
    f();
    return 0;
}

For sure I'm missing something, I'd appreciate if someone explains it to me. Regards

Answer 1

It turns out that in some compilers, with the right optimization flags, this actually won't cause a stack overflow! In fact, I tried compiling your program in g++. With optimization at defaults, it causes a stack overflow, but at optimization level -O3 it just goes into an infinite loop.

The reason that there's a difference between infinite recursion and infinite loops has to do with how the compiler, by default, implements these constructs. Loops historically have been implemented using branching instructions that tell the processor to pick up execution at a different part of the program. All these instructions do is jump the program counter someplace else, which just modifies the contents of a register. Function calls, on the other hand, are implemented by adding a new activation record to the stack to encode the arguments, return address, etc. so that when the function returns, it knows where to return to.

That said, this isn't "the way" that function calls or branches have to be implemented. You could, in theory, implement loops by using function calls and returns, though no compiler does so. Similarly, with functions that are tail-recursive (as is your example), compilers are often smart enough to elide all of the stack manipulations and to convert it to a naive branch instruction to avoid the overhead of stack setup and teardown.

In short, the reason you get different behavior is based on how the compiler decides to implement the code. If it's smart enough to see that it doesn't need to do an expensive function call setup, then it will convert the call into a simple loop instruction and loop forever. If it doesn't detect this, then it will fall back on the naive function call mechanism.

Answer 2

You aren't missing anything. Compile the program using gcc -O2 and there is no stack overflow.

Answer 3

It still needs to push the program counter on the stack each time a new function is called. That is one of the reason why the stack grows at each function invocation.

Answer 4

My guess is that C compiler writers probably do not feel it highly necessary to optimize the output of infinitely recursive calls to empty functions...

Answer 5

C is not required to eliminate tail calls. (Scheme is required to perform TCO.)

Answer 6

I think that it really is a question of the compiler then and how optimized it is. I would imagine that in both cases, a while loop and this endlessly recursive call, the machine instructions written are as explicitly as possible converting your wishes into instructions. As you know, for the while loop, the you are just jmp'ing back to the specific location and continuing from there. with the recursive call, you are pushing on a new value on the stack, so, per your question, I guess its really a question of how smart your compiler is ...