我正在研究一个用 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);
}
}
}
最佳答案
I want to know that is this normal?
是的。筹码量只有这么多。
In the code below, removing local variable neighbor can prevent from stack overflow?
没有。即使没有变量也没有返回值,函数调用本身也必须存储在堆栈中,以便最终可以展开堆栈。
例如……
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
In general how many recursive function calls causes stack overflow?
这取决于您的环境和函数调用。在 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
关于c - 有多少递归函数调用导致堆栈溢出?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48178640/