Stack overflow caused by recursive function

问题:

Being a beginner to C++ programming and computer systems architecture, I'm still learning the basics of C++. Yesterday I read about recursive function, so I decided to write my own, here's what I wrote : (very basic)

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

}

And when I do this : int zero1 = returnZero(4793 ); it causes a stack overflow, however, if I pass the value 4792 as parameter, no overflow occurs.

Any ideas as to why ?

回答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.

回答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.

回答3:

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.

回答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.

回答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.

回答6:

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;
    }
}