Stack overflow caused by recursive function

Question

I'm a beginner in C++. Yesterday I read about recursive functions, so I decided to write my own. Here's what I wrote:

int returnZero(int anyNumber) {
    if(anyNumber == 0)
        return 0;
    else  {
        anyNumber--;
        return returnZero(anyNumber);
    }
}

When I do this: int zero1 = returnZero(4793);, it causes a stack overflow. However, if I pass the value 4792 as the argument, no overflow occurs.

Any ideas as to why?

Solution 1

Whenever you call a function, including recursively, the return address and often the arguments are pushed onto the call stack. The stack is finite, so if the recursion is too deep you'll eventually run out of stack space.

What surprises me is that it only takes 4793 calls on your machine to overflow the stack. This is a pretty small stack. By way of comparison, running the same code on my computer requires ~100x as many calls before the program crashes.

The size of the stack is configurable. On Unix, the command is ulimit -s.

Given that the function is tail-recursive, some compilers might be able to optimize the recursive call away by turning it into a jump. Some compilers might take your example even further: when asked for maximum optimizations, gcc 4.7.2 transforms the entire function into:

int returnZero(int anyNumber) {
  return 0;
}

This requires exactly two assembly instructions:

_returnZero:
        xorl    %eax, %eax
        ret

Pretty neat.

Solution 2

You just hit the call stack's size limit of your system, that's what's happening. For some reason the stack in your system is tiny, a depth of 4793 function calls is rather small.

Solution 3

Your stack is limited in size and so when you make 4793 calls you are hitting the limit while 4792 just comes in under. Each function call will use some space on the stack for house keeping and maybe arguments.

This page gives an example of what a stack looks like during a recursive function call.

Solution 4

My guess is you stack is exactly big enough to fit 4792 entries - today. Tomorrow or the next, that number might be different. Recursive programming can be dangerous and this example illistrates why. We try not to let recursion get this deep or 'bad' things can happen.

Solution 5

Any "boundless" recursion, that is recursive calls that aren't naturally limited to a small(ish) number will have this effect. Exactly where the limit goes depends on the OS, the environment the function is called in (the compiler, which function calls the recursive function, etc, etc).

If you add another variable, say int x[10]; to your function that calls your recursive function, the number needed to crash it will change (probably by about 5 or so).

Compile it with a different compiler (or even different compiler settings, e.g. optimization turned on) and it will probably change again.

View more solutions

Comments

[Listing]

Maybe the bigger value is exactly whats needed to overflow the stack?

[Silas]

Try 5000 - it will most likely overflow the stack as well. How much memory does your system have?

[Drew Dormann]

Are you asking why your stack has a particular size?

[Fernando]

He says it works for i = 4793, so it should work for i = 4792...or no?

[charles]

I thought that once the function recursively called itself the stack frame created by that original function call would be poped off the stack. Is this not the case ? Also thanks for the reply.

[NPE]

@charles: In the general case, it can't be. A sufficiently good compiler would be able to optimize some cases, such as tail recursion: en.wikipedia.org/wiki/Tail_call

[charles]

NPE - aah fantastic. I never would have guessed. Last question, at each recursive call, does the new call create a new stack frame or just use the original one created ?

[NPE]

@charles: New stack frame. Just like any other function call.

[Spade 000]

Is it possible to allocate the function on the heap, rather on the stack? (to prevent stack overflow)