Given the C program with infinite recursion:
int main() {
main();
return 0;
}
Why would this result in a stack overflow. I know this results in undefined behaviour in C++ from the following thread Is this infinite recursion UB? (and as side node one can't call main()
in C++). However, valgrind tells me this leads to a stack overflow:
Stack overflow in thread 1: can't grow stack to 0x7fe801ff8
and then finally the program ends due to a segmentation error:
==2907== Process terminating with default action of signal 11 (SIGSEGV)
==2907== Access not within mapped region at address 0x7FE801FF0
Is this also undefined behavior in C, or should this really lead to a stack overflow and then why does this result in a stack overflow?
edit
1 I would like to know is infinite recursion allowed in C?
2 Should this result in a stack overflow? (has been sufficiently answered)
infinite recursion (countable and uncountable, plural infinite recursions) (programming) Any recursion that continues without end.
Iteration and recursion can occur infinitely: An infinite loop occurs with iteration if the loop-continuation test never becomes false; infinite recursion occurs if the recursion step does not reduce the problem in a manner that converges on the base case.
To prevent infinite recursion, you need at least one branch (i.e. of an if/else statement) that does not make a recursive call. Branches without recursive calls are called base cases; branches with recursive calls are called recursive cases. Functions can also be mutually recursive.
When the value of N becomes 0, because of the base condition, the recursion terminates. Infinite Recursion: Infinite Recursion occurs when the recursion does not terminate after a finite number of recursive calls. As the base condition is never met, the recursion carries on infinitely.
Whenever you call a function, the arguments are pushed on the stack, which means that data on the stack segment is "allocated". When the function is called, the return adress is also pushed on the stack, by the CPU, so it knows where to return to.
In your example case this means, that no arguments are used, so the only thing that is pushed is the return adress, which is rather small (4 bytes on x86-32 architexture), and additionally the stackframe is adjusted which takes another four bytes on this architecture.
From this is follows that, once the stack segment is exhausted, the function can not be called aynmore and an exception is raised to the OS. Now there can happen two things. Either the OS forwards the exception back to your application which you will see as stack overflow. Or the OS can try to allocate additional space for the stack segemnt, up to a defined limit, after which the application will see the stack overflow.
So this code (I renamed it to infinite_recursion() as main() can not be called) ...
int inifinite_recursion(void)
{
inifinite_recursion();
return 0;
}
... looks like this:
_inifinite_recursion:
push ebp ; 4 bytes on the stack
mov ebp, esp
call _inifinite_recursion ; another 4 bytes on the stack
mov eax, 0 ; this will never be executed.
pop ebp
ret
UPDATE
Regarding the standard C99 for defining recursion, the best I found so far is in Section 6.5.2.2 Paragraph 11:
Recursive function calls shall be permitted, both directly and indirectly through any chain of other functions.
Of course this doesn't answer whether it is defined what happens when the stack overflows. However at least it allows main
to be called recursively, while this is explicitly forbidden in C++ (Section 3.6.1 Paragraph 3 and Section 5.2.2 Paragraph 9).
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With