16

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)

16
  • 1
    Calling a function in C usually pushes some informations on the stack. So infinitely calling a function in C usually pushes a lot of informations on the stack, eventually leading to an overflow.
    – Nbr44
    Aug 14, 2013 at 8:53
  • You do understand how the call stack and function calls work, right? If not, read the Wikipedia article on "Call stacks" first.
    – DarkDust
    Aug 14, 2013 at 8:53
  • But maybe your confusion stems from the fact that tail recursions can be optimized to not use another stack frame?
    – DarkDust
    Aug 14, 2013 at 8:56
  • @DarkDust I don't know exactly how the call stack works (thanks for the reference). I can image c++ inline functions would fill the stack because they are expanded inline, but I couldn't imagine why this happens in C as well. Aug 14, 2013 at 9:02
  • 2
    You're very confused. Inline functions specifically would NOT increase the stack. Ordinary function calls pass parameters on the stack--in any language. Even in pure machine code or assembly, infinite recursion would overflow the stack because that's where the processor puts return addresses. Aug 14, 2013 at 9:25

15 Answers 15

16
+50

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

5
  • 2
    At first thanks for your elaborate answer! In C main can be called it is allowed by gcc even when compiling with -Wall -Wextra -pedantic without any warning are produced, this is different from C++, there you can't call main. otherwise I would have used a function void foo(void) I made sure I posted compilable code. Aug 14, 2013 at 9:41
  • I tried to compile it with gcc and got an error. Strangely I tried it again now, to see the error and it worked. Don't know why it didn't work the first time. It said something along the lines of "ANSIC C forbids taking the address of main" so mayb I misstyped something without noticing. But could be that I compiled it with g++ instead, because right now I made sure that it was with a C project.
    – Devolus
    Aug 14, 2013 at 12:11
  • Yeah, so I took the wrong template. Anyway, for the answer it doesn't really matter anyway. :)
    – Devolus
    Aug 14, 2013 at 12:26
  • Does this mean you cannot write a game loop that lasts forever?
    – chrs
    Aug 23, 2013 at 9:12
  • Of course you can. You just cant write a game loop thta continously starts itself, instead of processing data. ;)
    – Devolus
    Aug 23, 2013 at 10:56
10

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

1
  • Null pointer dereferences are undecidable too, and are clearly Undefined Behaviour in C. Your point? Jun 24, 2017 at 13:08
6

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.

  • Calling a function recursively is permitted (C.11 §6.5.2.2 ¶11)

Recursive function calls shall be permitted, both directly and indirectly through any chain of other functions.

  • Recursive entry into a statement creates new instances of local variables (C.11 §6.2.4 ¶5,6,7)

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.

3

Whenever you make a function call (including main()), the function call "info" (e.g. arguments) is pushed on top of the stack. This info is popped off the stack when the function returns. But as you can see in your code, you make a recursive call to main before you return, so stack keeps on growing until it hits its limit and hence the segmentation error.

The size of the stack is often limited and decided before runtime (e.g. by your operating system).

This means that stack overflow is not limited to main(), but to any other recursive functions without a proper way to terminate its tree (i.e. base cases).

3

Addressing questions 1:

I would like to know is infinite recursion allowed in C?

This article Compilers and Termination Revisited by John Regehr is answer on whether the C standard allows infinite recursion or not and after combing through the standard it is not too surprising to me that conclusions is that it is ambiguous. The article main thrust is about infinite loops and whether it is supported by the standard of various languages(including C and C++) to have non-terminating executions. As far as I can tell the discussion applies to infinite recursion just as well, of course assuming we can avoid a stack overflow.

Unlike C++ which says in section 1.10 Multi-threaded executions and data races paragraph 24:

The implementation may assume that any thread will eventually do one of the
following:
  — terminate,
  [...]

Which seems to rule out infinite recursion in C++. The draft C99 standard says in section 6.5.2.2 Function calls paragraph 11:

Recursive function calls shall be permitted, both directly and indirectly through any chain of other functions.

which does not put any limits on recursion and says this in section 5.1.2.3 Program execution paragraph 5:

The least requirements on a conforming implementation are:
— At sequence points, volatile objects are stable in the sense that previous 
  accesses are complete and subsequent accesses have not yet occurred.
— At program termination, all data written into files shall be identical to the
  result that execution of the program according to the abstract semantics would
  have  produced.
— The input and output dynamics of interactive devices shall take place as
  specified in 7.19.3. The intent of these requirements is that unbuffered or     
  line-buffered output appear as soon as possible, to ensure that prompting
  messages actually appear prior to a program waiting for input.

As the article says, the first condition should be straight forward to meet, the third condition according to the article does not really cover termination. So we are left with the second condition to deal with. According to the article it is ambiguous, the quote from the article is as follows:

If it is talking about termination of the program running on the abstract machine, then it is vacuously met because our program does not terminate. If it is talking about termination of the actual program generated by the compiler, then the C implementation is buggy because the data written into files (stdout is a file) differs from the data written by the abstract machine. (This reading is due to Hans Boehm; I had failed to tease this subtlety out of the standard.)

So there you have it: the compiler vendors are reading the standard one way, and others (like me) read it the other way. It’s pretty clear that the standard is flawed: it should, like C++ or Java, be unambiguous about whether this behavior is permitted.

Since it seems like there are two reasonable yet conflicting interpretations of the second condition the standard is deficient and should define explicitly whether this behavior is permitted.

2

Even if the function does not use stack space for local variables or argument passing, it still needs to store the return address and (possibly) the frame's base pointer (with gcc, this can be disabled via -fomit-frame-pointer).

On high enough optimization levels, the compiler might be able to re-write the recursion into a loop if the tail-call optimization in applicable, which would avoid the stack overflow.

9
  • This doesn't seem work for calling main(), but it indeed works for void foo(){foo();} when compiled with ` -Wall -pedantic -O3 -fomit-frame-pointer`. Is this because because my main returns int which has to be stored on the stack? Aug 14, 2013 at 9:18
  • depending on calling convention, 'small' return values (in particular scalar types) will be returned in registers, so they won't consume stack space; however, it's not a tail call because the code that sets the register to 0 needs to follow the recursive call, so TCO is not applicaple; a sufficiently smart optimizer however could figure out that the return value is constant and not generate recursive calls; in fact, clang will just optimize the whole thing away (which it's free to do as infinite recursion is UB)
    – Christoph
    Aug 14, 2013 at 9:36
  • actually, I'm not sure infinite recursion are UB - the C standard says Recursive function calls shall be permitted, both directly and indirectly through any chain of other functions.
    – Christoph
    Aug 14, 2013 at 9:43
  • That is exactly why I asked the question! :), although the stackoverflow will kill the program ofcourse. Aug 14, 2013 at 9:44
  • it should be undefined behaviour (or something along the lines may raise an implementation defined signal), but I couldn't find any standard quote (yet?); if it's not, I'd consider that a defect of the C standard
    – Christoph
    Aug 14, 2013 at 9:46
1

The stack section of the main memory is not infinite, so if you call a function recursively an indefinite number of times, the stack will be filled of informations about each single function invocation. This lead to a Stack Overflow, when there's no more space to use for any other function invocation.

1

Its important to understand how the calling stack of functions in C looks like:

function stack

1

Is infinite recursion allowed in C? The simple answer is Yes. The compiler will allow you to call a function infinitely until you run out of stack space; it will not prevent you from doing this.

Is infinite recursion possible? No. As pointed out already, each call to a function requires a return address to be pushed on the program stack, along with any parameters the function requires to operate. Your program only has a limited stack size and once you use up your stack your application will fail.

Is fake infinite recursion possible? Yes. It is possible to design a function which calls itself 1000 times and then allows itself to exit from the 1000 function calls, so that the stack only has the original function call on the stack... and then repeat the whole process all over again in a infinite loop. I don't consider this real infinite recursion though.

1

Infinite recursion is allowed in C. At compile time, the compiler will allow this, but you may get a runtime error upon doing so.

1

It's allowed in c, since the standard says ->

Recursive function calls shall be permitted, both directly and indirectly through any chain of other functions.

In 6.5.2.2 -> 11

and the Stackoverflow happens simply, because each state of the calling scope, has to get stored, so if infinite states of scope have to be stored, your anywhen running out of memory, as you don't have infinite memory space. And this is defined behavior, because it is happening on runtime, and the compiler doesn't need to check in respect of the standard, if the recursion ever gets broken.

0

Cause stack is limited and whenever you call a function it saves the callee (by pushing base pointer onto stack and copying current stack pointer as new base pointer value) therefore consumes stack will overflow with infinite number of calls. See the calling convention and how stack reacts at here (http://www.csee.umbc.edu/~chang/cs313.s02/stack.shtml)

0

I just looked at copy a recent draft c standards doc and none of the recursion references talk about infinite recursion.

If the standard document doesn't require the compiler to support something and doesn't ban it, then compiler developers will consider this undefined behavior.

0
#include<iostream>
using namespace std;

int a();
int b();


int a()
{
    cout<<"Hello World\n";
    b();
    return 0;
}
int b()
{
    cout<<"Hello World\n";
    a();
    return 0;
}
void print(int b)
{
   cout << b << endl;
}
int main()
{
   int b = a();
   print(b);
   return 0;
}

This code returns this output in DevC++:

Process exited after 14.04 seconds with return value 3221225725

You can check here for what' the meaning of this value Dev C++ Process exited with return value 3221225725

So function calls in C++ binding every function in call stack . Also you know, this is limited size, every fuction call raise this size.

0
==2907== Process terminating with default action of signal 11 (SIGSEGV)
==2907==  Access not within mapped region at address 0x7FE801FF0

What this means is the stack has grown so much due to the recursive calls and increments of rsp that it is has accessed a memory address outside of the virtual memory that the process mapped for the thread stack. The page fault handler will notice that the process hasn't allocated this region of virtual memory and will propagate the exception to the program by calling kernel exception and stack unwinding procedures. On windows, the top level SEH handler will then be invoked from the kernel32.dll .pdata section which will call an UnhandledExceptionFilter which can be set from application code using SetUnhandledExceptionFilter. This routine specified by the application can call GetExceptionCode to switch the exception constant and display relevant modal error dialog boxes.

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.