有多少递归函数调用会导致堆栈溢出？

Question

我正在研究一个用 c 编写的模拟问题，我的程序的主要部分是一个递归函数。当递归深度达到大约 500000 时，似乎发生堆栈溢出。

Q1 : 我想知道这正常吗？

Q2：一般有多少递归函数调用会导致堆栈溢出？

Q3：在下面的代码中，删除局部变量neighbor可以防止堆栈溢出吗？

我的代码：

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

Answer 1

我想知道这正常吗？

是的。只有这么多的堆栈大小。

在下面的代码中，删除局部变量邻居可以防止堆栈溢出吗？

不。即使没有变量和返回值，函数调用本身也必须存储在堆栈中，以便最终可以展开堆栈。

例如...

void recurse() {
    recurse();
}

int main (void)
{
    recurse();
}

这仍然会溢出堆栈。

$ ./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

一般来说，有多少递归函数调用会导致堆栈溢出？

这取决于您的环境和函数调用。在 OS X 10.13 上，我默认限制为 8192K。

$ ulimit -s
8192

这个简单的例子clang -g可以递归 261976 次。由于-O3我无法让它溢出，我怀疑编译器优化已经消除了我的简单递归。

#include <stdio.h>

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

int main (void)
{
    recurse();
}

添加一个整数参数，它是 261933 次。

#include <stdio.h>

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

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

添加一个双参数，现在是 174622 次。

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

添加一些堆栈变量，它是 104773 次。

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

等等。但是我可以在这个 shell 中增加我的堆栈大小并获得两倍的调用。

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

对于 65,532K 或 64M 的堆栈，我有一个严格的上限。

$ ulimit -Hs
65532