6

In order to know the limit of the recursive calls in C++ i tried this function !

void recurse ( int count ) // Each call gets its own count
{
printf("%d\n",count );
  // It is not necessary to increment count since each function's
  //  variables are separate (so each count will be initialized one greater)
  recurse ( count + 1 );
}

this program halt when count is equal 4716 ! so the limit is just 4716 !! I'm a little bit confused !! why the program stops exeuction when the count is equal to 4716 !! PS: Executed under Visual studio 2010. thanks

satyres
  • 377
  • 1
  • 5
  • 17

3 Answers3

12

The limit of recursive calls depends on the size of the stack. The C++ language is not limiting this (from memory, there is a lower limit of how many function calls a standards conforming compiler will need to support, and it's a pretty small value).

And yes, recursing "infinitely" will stop at some point or another. I'm not entirely sure what else you expect.

It is worth noting that designing software to do "boundless" recursion (or recursion that runs in to the hundreds or thousands) is a very bad idea. There is no (standard) way to find out the limit of the stack, and you can't recover from a stack overflow crash.

You will also find that if you add an array or some other data structure [and use it, so it doesn't get optimized out], the recursion limit goes lower, because each stack-frame uses more space on the stack.

Edit: I actually would expect a higher limit, I suspect you are compiling your code in debug mode. If you compile it in release mode, I expect you get several thousand more, possibly even endless, because the compiler converts your tail-recursion into a loop.

Mats Petersson
  • 126,704
  • 14
  • 140
  • 227
  • Boundless recursion is possible on some targets. GCC supports something called "split stacks", which allows stacks to grow, *discontiguously,* to fill available memory. See http://gcc.gnu.org/wiki/SplitStacks – Dietrich Epp Apr 20 '13 at 23:26
  • I know there was a limit but i wonder what is this limit ! i did not expected that the stack will explode in less than 5000 calls ! thanks for the explanation ! – satyres Apr 20 '13 at 23:27
  • There is still a limit, and there is still (as far as I understand) no way to detect running out of stack. Using a software stack, there is at least a way to detect when the stack runs out... – Mats Petersson Apr 20 '13 at 23:28
  • 2
    @Satyres: If you compile in "release" rather than debug, I expect it will be MUCH larger. In debug mode, the compiler adds extra "dummy" stack space to detect stack overwrites, which makes each stackframe about 200 bytes (200 * nearly 5000 = 1MB, so makes some sense), where without that, the stack frame should only be about 4-16 bytes, and you should be able to do many thousands more. It may be that you have to turn off some other feature as well - it's been a while since I last used visual studio... – Mats Petersson Apr 20 '13 at 23:30
  • 1
    @MatsPetersson: You are right my friend ! thanks for your comment, so the limit will be the size max of an int (32bit) – satyres Apr 20 '13 at 23:40
2

The stack size is dependent on your environment.

In *NIX for instance, you can modify the stack size in the environment, then run your program and the result will be different.

In Windows, you can change it this way (source):

$ editbin /STACK:reserve[,commit] program.exe
Community
  • 1
  • 1
Intrepidd
  • 19,772
  • 6
  • 55
  • 63
1

You've probably run out of stack space.

Every time you call the recursive function, it needs to push a return address on the stack so it knows where to return to after the function call.

It crashes at 4716 because it just happens to run out of stack space after about 4716 iterations.

tangrs
  • 9,709
  • 1
  • 38
  • 53
  • but it's too small !! just 5000 calls !! how to know the max size of the stack ! – satyres Apr 20 '13 at 23:22
  • I thought the stack size was related to the memory size of the computer ! so i have to change it in VS2010 ! – satyres Apr 20 '13 at 23:24
  • 1
    The default stack size is normally set in the executable file. I don't know where you got the idea that it's related to how much memory the computer has. – tangrs Apr 20 '13 at 23:26