3

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

6 Answers 6

5

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.

Sign up to request clarification or add additional context in comments.

5 Comments

Hey thanks :D. This is a very helpful and complete explanation, yes that's pretty much what I was concerned about: how smart the compiler could be in these cases.
@Nicolas- Glad to help out! BTW, if you like any of the answers here (even if it isn't mine), you should accept it so that the question is marked resolved.
Done xD. I'm still learning to navigate this site lol. I liked pretty much all the answers, yours is the most complete though thanks ^^
You cannot implement loops with function call and return. It's easy to construct a strictly conforming program that loops N times for values of N insanely large relative to the representation space of void * (which by a simple argument bounds the number of levels of recursion), and it is not conforming for an implementation to crash with a stack overflow when running such a program.
Nitpick - should replace g++ with gcc.
4

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

1 Comment

hey thanks. Lol I guess next time I'll try the command line options for my compiler.
0

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.

1 Comment

thanks :D Mm I forgot about the PC yeah, but it's like there's no need for remembering all the values in this particular example I think.
0

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...

1 Comment

Lol yes, this example is pretty much useless. But I think it might come in handy to optimize that calls in some special cases.
0

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

1 Comment

Thanks :D Nice to know. I'll investigate that further
0

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 ...

1 Comment

thanks :D Yeah, my concerns exactly I was kinda surprised when the compilers I tried didn't optimize that, I guess it was my fault for not using the appropiate parameters lol.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.