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)

Solution 1:

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

Solution 2:

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