4

I am working on a simulation problem written in c, the main part of my program is a recursive function. when the recursive depth reaches approximately 500000 it seems stack overflow occurs.

Q1 : I want to know that is this normal?

Q2 : in general how many recursive function calls causes stack overflow?

Q3 : in the code below, removing local variable neighbor can prevent from stack overflow?

my code:

/*
 * recursive function to form Wolff Cluster(= WC)
 */
void grow_Wolff_cluster(lattic* l, Wolff* wolff, site *seed){

    /*a neighbor of site seed*/
    site* neighbor;

    /*go through all neighbors of seed*/
    for (int i = 0 ; i < neighbors ; ++i) {


        neighbor = seed->neighbors[i];

        /*add to WC according to the Wolff Algorithm*/
        if(neighbor->spin == seed->spin && neighbor->WC == -1 && ((double)rand() / RAND_MAX) < add_probability)
        {
            wolff->Wolff_cluster[wolff->WC_pos] = neighbor;
            wolff->WC_pos++;                  // the number of sites that is added to WC
            neighbor->WC = 1;          // for avoiding of multiple addition of site
            neighbor->X = 0;


            ///controller_site_added_to_WC();


            /*continue growing Wolff cluster(recursion)*/
            grow_Wolff_cluster(l, wolff, neighbor);
        }
    }
}
Improve this question
6
  • How many? Until the stack is used up. Under Windows the system can add additional memory, so... it may take really a lot. In your case, you don't have many local variables (only a pointer), so it's just this pointer and the function frame - really too little. Commented Jan 10, 2018 at 0:32
  • is it normal to have stack overflow after 500000 recursive calls ?on CentOs 7 Commented Jan 10, 2018 at 0:34
  • This looks awfully familiar ... 500k calls would do it, but it completely depends on your system's stack size and what you're pushing there, take a look here Commented Jan 10, 2018 at 0:35
  • If you ever need more than 100 levels of recursion, then recursion isn't the right solution to your problem (not counting "tail" recursion which most decent compilers will convert to iteration for you). Commented Jan 10, 2018 at 0:45
  • 1
    The default stack size on a Linux machine is 8 MiB. If you need more than about 16 bytes of data per call (including return addresses etc), you'd be running into problems at 500,000 calls deep (but not at 500,000 calls if you've returned from 499,900 of them already). It is the number of levels of recursive call that cause trouble - stack overflows - and not the total number of calls. Commented Jan 10, 2018 at 0:47

5 Answers 5

Reset to default
14

I want to know that is this normal?

Yes. There's only so much stack size.

In the code below, removing local variable neighbor can prevent from stack overflow?

No. Even with no variables and no return values the function calls themselves must be stored in the stack so the stack can eventually be unwound.

For example...

void recurse() {
    recurse();
}

int main (void)
{
    recurse();
}

This still overflows the stack.

$ ./test
ASAN:DEADLYSIGNAL
=================================================================
==94371==ERROR: AddressSanitizer: stack-overflow on address 0x7ffee7f80ff8 (pc 0x00010747ff14 bp 0x7ffee7f81000 sp 0x7ffee7f81000 T0)
    #0 0x10747ff13 in recurse (/Users/schwern/tmp/./test+0x100000f13)

SUMMARY: AddressSanitizer: stack-overflow (/Users/schwern/tmp/./test+0x100000f13) in recurse
==94371==ABORTING
Abort trap: 6

In general how many recursive function calls causes stack overflow?

That depends on your environment and function calls. Here on OS X 10.13 I'm limited to 8192K by default.

$ ulimit -s
8192

This simple example with clang -g can recurse 261976 times. With -O3 I can't get it to overflow, I suspect compiler optimizations have eliminated my simple recursion.

#include <stdio.h>

void recurse() {
    puts("Recurse");
    recurse();
}

int main (void)
{
    recurse();
}

Add an integer argument and it's 261933 times.

#include <stdio.h>

void recurse(int cnt) {
    printf("Recurse %d\n", cnt);
    recurse(++cnt);
}

int main (void)
{
    recurse(1);
}

Add a double argument, now it's 174622 times.

#include <stdio.h>

void recurse(int cnt, double foo) {
    printf("Recurse %d %f\n", cnt, foo);
    recurse(++cnt, foo);
}

int main (void)
{
    recurse(1, 2.3);
}

Add some stack variables and it's 104773 times.

#include <stdio.h>

void recurse(int cnt, double foo) {
    double this = 42.0;
    double that = 41.0;
    double other = 40.0;
    double thing = 39.0;
    printf("Recurse %d %f %f %f %f %f\n", cnt, foo, this, that, other, thing);
    recurse(++cnt, foo);
}

int main (void)
{
    recurse(1, 2.3);
}

And so on. But I can increase my stack size in this shell and get twice the calls.

$ ./test 2> /dev/null | wc -l
174622
$ ulimit -s 16384
$ ./test 2> /dev/null | wc -l
349385

I have a hard upper limit to how big I can make the stack of 65,532K or 64M.

$ ulimit -Hs
65532
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Note: My results are with -g. With -O3 I can't get the stack to overflow. I suspect the compiler has optimized away my simple recursion.
3

A stack overflow isn’t defined by the C standard, but by the implementation. The C standard defines a language with unlimited stack space (among other resources) but does have a section about how implementations are allowed to impose limits.

Usually it’s the operating system that actually first creates the error. The OS doesn’t care about how many calls you make, but about the total size of the stack. The stack is composed of stack frames, one for each function call. Usually a stack frame consists of some combination of the following five things (as an approximation; details can vary a lot between systems):

  1. The parameters to the function call (probably not actually here, in this case; they’re probably in registers, although this doesn’t actually buy anything with recursion).
  2. The return address of the function call (in this case, the address of the ++i instruction in the for loop).
  3. The base pointer where the previous stack frame starts
  4. Local variables (at least those that don’t go in registers)
  5. Any registers the caller wants to save when it makes a new function call, so the called function doesn’t overwrite them (some registers may be saved by the caller instead, but it doesn’t particularly matter for stack size analysis). This is why passing parameters in registers doesn’t help much in this case; they’ll end up on the stack sooner or later.

Because some of these (specifically, 1., 4., and 5.) can vary in size by a lot, it can be difficult to estimate how big an average stack frame is, although it’s easier in this case because of the recursion. Different systems also have different stack sizes; it currently looks like by default I can have 8 MiB for a stack, but an embedded system would probably have a lot less.

This also explains why removing a local variable gives you more available function calls; you reduced the size of each of the 500,000 stack frames.

If you want to increase the amount of stack space available, look into the setrlimit(2) function (on Linux like the OP; it may be different on other systems). First, though, you might want to try debugging and refactoring to make sure you need all that stack space.

Improve this answer

2 Comments

This is nicely written, but it does not answer the numbered questions in OP’s question or explain the mistaken concepts inherent in them. E.g., Q1: Yes, it is normal for many calls to overflow the stack. Q2: The number of calls it takes to overflow the stack depends on how much space each function needs. Q3: Removing neighbor could reduce the space one call uses and increase the number of calls that could be made before overflow occurs, but it will not prevent it. None of these are addressed directly in this answer.
@EricPostpischil I don’t have them nicely numbered, but I did address all of them. Respectively, by answers are “It’s normal for a lot of calls to overwhelm the stack, but I don’t know if 500,000 is a reasonable number in your environment”, “It’s not the number of calls that’s relevant but the frame size”, and “Removing neighbor reduces frame size so makes the number of calls needed to get an overflow higher”.
2

  1. Yes and no - if you come across a stack overflow in your code, it could mean a few things

    • Your algorithm is not implemented in a way that respects the amount of memory on the stack you have been given. You may adjust this amount to suit the needs of the algorithm.

      If this is the case, it's more common to change the algorithm to more efficiently utilize the stack, rather than add more memory. Converting a recursive function to an iterative one, for example, saves a lot of precious memory.

    • It's a bug trying to eat all your RAM. You forgot a base case in the recursion or mistakenly called the same function. We've all done it at least 2 times.

  2. It's not necessarily how many calls cause an overflow - it's dependent upon how much memory each individual call takes up on a stack frame. Each function call uses up stack memory until the call returns. Stack memory is statically allocated -- you can't change it at runtime (in a sane world). It's a last-in-first-out (LIFO) data structure behind the scenes.

  3. It's not preventing it, it's just changing how many calls to grow_Wolff_cluster it takes to overflow the stack memory. On a 32-bit system, removing neighbor from the function costs a call to grow_Wolff_cluster 4 bytes less. It adds up quickly when you multiply that in the hundreds of thousands.

I suggest you learn more about how stacks work for you. Here's a good resource over on the software engineering stack exchange. And another here on stack overflow (zing!)

Improve this answer

15 Comments

thank you for your answer, my code is fine, but the algorithm that I use must be implemented with recursive function, and for small recursive depth i have no problem and my results is good.
Since stack size is a settable value in most environments, your answer to 1 is not convincing. i.e. Stack overflow does not necessarily mean wrong code. It just means the stack size needs to be adjusted up for that particular application.
@ryyker I can see that interpretation. I'll update my wording a bit.
Regarding 1, systems often limit stack size more than actually necessary. You might have an entirely good algorithm that simply requires recursion, and re-implementing it as a loop with a stack structure on the heap would let it work on much larger amounts of data.
Yes, the content of your answer is good, but the comments under your answer are spectacular :)
|
0

For each time a function recurs, your program takes more memory on the stack, the memory it takes for each function depends upon the function and variables within it. The number of recursions that can be done of a function is entirely dependant upon your system.

There is no general number of recursions that will cause stack overflow.

Removing the variable 'neighbour' will allow for the function to recur further as each recursion takes less memory, but it will still eventually cause stack overflow.

Improve this answer

3 Comments

my system is Centos 7 , RAM 4 GB, possessor core i7, 500000 recursive calls in enough to stack overflow in this system?
@mehrdad - Why don't you try it and find out?
@mehrdad Check ulimit -s.
0

This is a simple c# function that will show you how many iteration your computer can take before stack overflow (as a reference, I have run up to 10478):

    private void button3_Click(object sender, EventArgs e)
    {
        Int32 lngMax = 0;
        StackIt(ref lngMax);
    }

    private void StackIt(ref Int32 plngMax, Int32 plngStack = 0)
    {
        if (plngStack > plngMax)
        {
            plngMax = plngStack;
            Console.WriteLine(plngMax.ToString());
        }

        plngStack++;
        StackIt(ref plngMax, plngStack);
    }

in this simple case, the condition check: "if (plngStack > plngMax)" could be removed, but if you got a real recursive function, this check will help you localize the problem.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.