Limited recursion in C?

Question

I ran this program and it output

...

65088
65089
65090

and then it stopped. Windows 7 said a.exe stopped working. Here is the code:

#include <stdio.h>

void go(void);

main()
{
    go();
}

void go(void)
{
    static int i = 0;
    printf("%d\n", i++);
    go();
}

I think this program should keep on printing numbers indefinitely due to recursion, but it stops at 65090! The C code is compiled with gcc. Any ideas?

Looks like you may have a stack overflow. Get it? Get it? =D — LainIwakura, Jun 24 '11 at 20:49
No error? Usually you'll see something. For example, I see a segmentation fault after about 327000 (varies each run). — Aaron Dufour, Jun 25 '11 at 02:13

Jason · Accepted Answer · 2011-06-24T20:21:36.513

You are going to overflow the stack at some point because each call to go() must push a return address on the stack even though you pass no arguments to the function call. So every call to go() is taking up a pointer-sized block on the stack for that return address. Since the stack has a limited size, that means at some point you're going to run out of space. The C-language does not specify that a tail-call optimization should take place for circumstances like this, although some compilers (like gcc) do offer that option via optimization switches. But that would be something that is compiler-specific, and independent of the language specification.

That last sentence doesn't really make sense. The C standard says nothing about optimization; that's entirely up to the compiler. — Oliver Charlesworth, Jun 24 '11 at 20:19

score 10 · Answer 2 · answered Jun 24 '11 at 20:16

10

It stops because it is overflowing the stack. Once you overflow the stack the results are undefined.

answered Jun 24 '11 at 20:16

cnicutar

178,505
25
365
392

the msvc compiler might do tail call optimization on this code if it's compiled with opimization (and thus not crash) – nos Jun 24 '11 at 20:18
1

A way you can achieve an infinite print like what you want would need to be done with a loop in main, not recursion, like: `while(true) { go(); }` , removing the recursion from the function itself of course – Dan F Jun 24 '11 at 20:19
@nos Yes, optimizations can hide a problem such as this one; but check out what happened here: http://stackoverflow.com/questions/6386601/given-that-b-is-always-non-zero-why-b-b-b-works-but-b-does-not/6386896 – cnicutar Jun 24 '11 at 20:20

score 7 · Answer 3 · answered Jun 24 '11 at 20:16

7

You cannot recurse infinitely on a machine with finite resources -- specifically, the stack. Each nested subroutine call required more stack space, and eventually you will run out.

answered Jun 24 '11 at 20:16

mah

39,056
9
76
93

1

Actually, one can with tail-call optimization... (granted, a feature not generally present in C, but the function *is* TCO'able). – Jun 24 '11 at 20:18
That is a compiler-specific optimization, not a language standard. So in order to get that type of functionality, you would have to provide the correct settings to your compiler, if it's supported. – Jason Jun 24 '11 at 20:20
@Jason Of course. C says nothing about it. I was simply challenging the assertion that "you cannot recurse infinitely on a machine with finite resources" ;-) – Jun 24 '11 at 20:22

score 2 · Answer 4 · answered Jun 24 '11 at 20:17

By "stopped working" do you mean crashed? That would make sense. Every program has a limited stack depth, and each level of recursion (i.e. each new function called) sets up itself on the stack. So if your program reached the maximum stack depth, it will crash!

score 2 · Answer 5 · answered Jun 24 '11 at 20:19

2

It appears your compiler does not perform any tail call optimizations. Even though there is no reason for the runtime system to maintain a stack of calls, it does so any way.

answered Jun 24 '11 at 20:19

sarnold

102,305
22
181
238

+1 ... just for the link. (The other answers are lacking in external resources :-/) – Jun 24 '11 at 20:25

score 1 · Answer 6 · answered Jun 24 '11 at 20:17

The recursion depth is limited by the program stack size. Each call pushes additional info to the stack, and when the stack is exhausted - it overflows. In your case you got 65090 frames in the stack before overflowing, once overflown- your program is dead.

score 1 · Answer 7 · answered Jun 24 '11 at 20:18

I think you've run out of space on your stack. Your program is only allowed a certain amount of memory (which your dev environment can probably change), and because go() is called within itself, 65000 copies of the function call exist at the same time.

score 1 · Answer 8 · edited May 23 '17 at 12:04

First of all, it's not C that limits the recursion. It's your Operating System!

This happens because recursion uses the stack. Do you know what the stack is? It's a memory region of the application that is used to store (local) variables, or parameters that must be send from one function to another during a function call. It also stores other informations, like the address of the function it must return to after executing the current one.

Now, you see, infinite recursion is a problem because more data is being stored on the stack after each recursion, and since these functions never return, their resources on stack are also never deallocated. At some point, the stack is going to run out of memory and it's going to explode in your face.

On Windows, if you need to increase the stack size you could try this.

score 0 · Answer 9 · answered Jun 24 '11 at 20:42

0

Regardless of whether this does recursion or not, once you reach INTMAX your program may do what it pleases since overflow of int is undefined behavior. And since a static analysis can show this, your whole program may do what pleases.

answered Jun 24 '11 at 20:42

Jens Gustedt

76,821
6
102
177

Limited recursion in C?

9 Answers9