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?

Maybe the bigger value is exactly whats needed to overflow the stack? — Listing, Apr 12 '13 at 16:23
Try 5000 - it will most likely overflow the stack as well. How much memory does your system have? — Silas, Apr 12 '13 at 16:24

NPE · Accepted Answer · 2013-04-12T16:39:49.197

46

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.

edited Apr 12 '13 at 16:39

answered Apr 12 '13 at 16:24

NPE

486,780
108
951
1,012

He says it works for i = 4793, so it should work for i = 4792...or no? – Fernando Apr 12 '13 at 16:25
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. – charles Apr 12 '13 at 16:34
1

@charles: In the general case, it can't be. A sufficiently good compiler would be able to optimize some cases, such as tail recursion: http://en.wikipedia.org/wiki/Tail_call – NPE Apr 12 '13 at 16:36
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 ? – charles Apr 12 '13 at 16:38
1

@charles: New stack frame. Just like any other function call. – NPE Apr 12 '13 at 16:40
Is it possible to allocate the function on the heap, rather on the stack? (to prevent stack overflow) – Spade 000 Feb 16 '21 at 04:39

Óscar López · Answer 2 · 2013-04-12T16:53:07.423

4

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.

edited Apr 12 '13 at 16:53

answered Apr 12 '13 at 16:24

Óscar López

232,561
37
312
386

Shafik Yaghmour · Answer 3 · 2013-04-12T16:39:26.950

2

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.

edited Apr 12 '13 at 16:39

answered Apr 12 '13 at 16:24

Shafik Yaghmour

154,301
39
440
740

score 1 · Answer 4 · answered Apr 12 '13 at 16:25

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.

score 1 · Answer 5 · answered Apr 12 '13 at 16:29

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.

score 0 · Answer 6 · edited Sep 28 '16 at 17:41

Using recursion, you can achieve SuperDigit:

public class SuperDigit
{
    static int sum = 0;

    int main()
    {
        int n = 8596854;
        cout<<getSum(n);
    }

    int getSum(int n){
        sum=0;
        while (n > 0) {
            int rem;
            rem = n % 10;
            sum = sum + rem;
            n = n / 10;
            getSum(n);
        }
        return sum;
    }
}

Stack overflow caused by recursive function

6 Answers6

Linked

Related