Infinite recursion in C
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)
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).
Whether a program recurses infinitely is not decidable. No sensible standard will ever require a property that may be impossible to verify even for conforming programs, so no C standard, current or future, will ever have anything to say about infinite recursion (just as no C standard will ever require conforming programs to eventually halt).
Recursion is a type of iteration that implicitly preserves local state before moving to the next iteration. It is easy enough to reason this through by thinking of just regular functions calling each other, one after the other:
void iteration_2 (int x) {
/* ... */
}
void iteration_1 (int x) {
if (x > 0) return;
iteration_2(x + 1);
}
void iteration_0 (int x) {
if (x > 0) return;
iteration_1(x + 1);
}
Each iteration_#() is basically identical to each other, but each one has it's own x , and each one remembers which function had called it, so it can properly return back to the caller when the function it calls is done. This notion doesn't change when the program is converted into a recursive version:
void iteration (int x) {
if (x > 0) return;
iteration(x + 1);
}
The iteration becomes infinite if the stopping condition (the if check to return from the function) is removed. There is no returning from the recursion. So the information that is remembered for each successive function call (the local x and the address of the caller) keeps piling on until the OS runs out of memory to store that information.
It is possible to implement an infinitely recursive function that does not overflow the "stack". At sufficient optimization levels, many compilers can apply an optimization to remove the memory needed to remember anything for a tail recursive call. For instance, consider the program:
int iteration () {
return iteration();
}
When compiled with gcc -O0 , it becomes:
iteration:
.LFB2:
pushq %rbp
.LCFI0:
movq %rsp, %rbp
.LCFI1:
movl $0, %eax
call iteration
leave
ret
But, when compiled with gcc -O2 , the recursive call is removed:
iteration:
.LFB2:
.p2align 4,,7
.L3:
jmp .L3
The result of this infinite recursion is a simple infinite loop, and there will be no overrun of the "stack". So, infinite recursion is allowed since infinite loops are allowed.
Your program, however, is not a candidate for tail call optimization, since the recursive call is not the last thing your function does. Your function still has a return statement that follows the recursive call. Since there is still code that needs to execute after the recursive call returns, the optimizer cannot remove the overhead of the recursive call. It must allow the call to return normally, so that the code after it may execute. So, your program will always pay the penalty of storing the return address of the calling code.
The standard does not speak to "infinite recursion" in any specific terms. I have collected together what I believe relevant to your question.
Recursive function calls shall be permitted, both directly and indirectly through any chain of other functions.
An object whose identifier is declared with no linkage and without the storage-class specifier static has automatic storage duration, as do some compound literals. ...
For such an object that does not have a variable length array type, its lifetime extends from entry into the block with which it is associated until execution of that block ends in any way. (Entering an enclosed block or calling a function suspends, but does not end, execution of the current block.) If the block is entered recursively, a new instance of the object is created each time. ...
For such an object that does have a variable length array type, its lifetime extends from the declaration of the object until execution of the program leaves the scope of the declaration. If the scope is entered recursively, a new instance of the object is created each time.
The standard talks about memory allocation failure in numerous places, but never in the context of an object with automatic storage duration. Anything not explicitly defined in the standard is undefined, so a program that fails to allocate an object with automatic storage duration has undefined behavior. This would apply equally between a program that just had a very long function call chain or too many recursive calls.
链接地址: http://www.djcxy.com/p/80504.html上一篇: GHC能否真的不内联地图，scanl，foldr等？
下一篇: C中的无限递归