how many recursive function calls causes stack overflow?

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

Solution

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