有多少递归函数调用导致堆栈溢出？
how many recursive function calls causes stack overflow?
我正在研究一个用 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);
}
}
}
每次函数重复出现时，您的程序都会在堆栈上占用更多内存，每个函数占用的内存取决于函数和其中的变量。函数可以完成的递归次数完全取决于您的系统。
没有一般的递归次数会导致栈溢出
删除变量 'neighbour' 将允许函数进一步递归，因为每次递归占用的内存更少，但最终仍会导致堆栈溢出。
是和否 - 如果您在代码中遇到堆栈溢出，这可能意味着一些事情
您的算法未以尊重您已获得的堆栈内存量的方式实现。您可以根据算法的需要调整此数量。
如果是这种情况，更常见的做法是更改算法以更有效地利用堆栈，而不是添加更多内存。例如，将递归函数转换为迭代函数可以节省大量宝贵的内存。
这是一个试图吃掉你所有 RAM 的错误。您忘记了递归中的基本情况或错误地调用了相同的函数。我们都完成了至少 2 次。
不一定有多少调用会导致溢出——这取决于每个单独的调用在堆栈帧上占用了多少内存。每个函数调用都会用完堆栈内存，直到调用 returns。堆栈内存是静态分配的——您不能在运行时更改它（在一个理智的世界中）。这是幕后的后进先出 (LIFO) 数据结构。
它并没有阻止它，它只是改变了对 grow_Wolff_cluster 的调用次数以溢出堆栈内存。在 32 位系统上，从函数中删除 neighbor 会使对 grow_Wolff_cluster 的调用减少 4 个字节。当你乘以数十万时，它加起来很快。
我建议您了解更多有关堆栈如何为您工作的信息。 Here's a good resource over on the software engineering stack exchange. And another here on stack overflow（兴奋！）
I want to know that is this normal?
是的。筹码量只有这么多。
In the code below, removing local variable neighbor can prevent from stack overflow?
没有。即使没有变量和 return 值，函数调用本身也必须存储在堆栈中，以便最终可以展开堆栈。
例如...
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 标准定义的，而是由实现定义的。 C 标准定义了一种具有无限堆栈的语言 space（以及其他资源），但确实有一节关于如何允许实现施加限制。
通常首先造成错误的是操作系统。 OS 并不关心你调用了多少次，而是关心堆栈的 总大小 。栈由栈帧组成，每个函数调用一个。通常堆栈帧由以下五种东西的某种组合组成（作为近似值；不同系统的细节可能有很大差异）：
- 函数调用的参数（在这种情况下可能实际上不在这里；它们可能在寄存器中，尽管这实际上并没有用递归购买任何东西）。
- 函数调用的return地址（本例为
for循环中++i指令的地址）。
- 上一个堆栈帧开始的基指针
- 局部变量（至少那些不进入寄存器的变量）
- 调用者在进行新的函数调用时想要保存的任何寄存器，因此被调用的函数不会覆盖它们（一些寄存器可能会被调用者保存，但它对堆栈大小并不特别重要分析）。这就是为什么在这种情况下在寄存器中传递参数没有多大帮助；他们迟早会进入堆栈。
因为其中一些（特别是 1.、4. 和 5.）的大小可能相差很大，所以很难估计平均堆栈帧有多大，尽管在这种情况下更容易因为递归。不同的系统也有不同的堆栈大小；目前看起来默认情况下我可以有 8 MiB 的堆栈，但嵌入式系统可能会少很多。
这也解释了为什么删除局部变量会为您提供更多可用的函数调用；您减少了 500,000 个堆栈帧中每个堆栈帧的大小。
如果您想增加可用的堆栈数量 space，请查看 setrlimit(2) function（在 Linux 上与 OP 类似；在其他系统上可能有所不同）。不过，首先，您可能想尝试调试和重构以确保您需要所有堆栈 space.
这是一个简单的 c# 函数，它会告诉你在堆栈溢出之前你的计算机可以进行多少次迭代（作为参考，我有 运行 最多 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);
}
在这种简单的情况下，条件检查："if (plngStack > plngMax)" 可以删除，
但是如果你有一个真正的递归函数，这个检查将帮助你定位问题。
我正在研究一个用 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);
}
}
}
每次函数重复出现时，您的程序都会在堆栈上占用更多内存，每个函数占用的内存取决于函数和其中的变量。函数可以完成的递归次数完全取决于您的系统。
没有一般的递归次数会导致栈溢出
删除变量 'neighbour' 将允许函数进一步递归，因为每次递归占用的内存更少，但最终仍会导致堆栈溢出。
是和否 - 如果您在代码中遇到堆栈溢出，这可能意味着一些事情
您的算法未以尊重您已获得的堆栈内存量的方式实现。您可以根据算法的需要调整此数量。
如果是这种情况，更常见的做法是更改算法以更有效地利用堆栈，而不是添加更多内存。例如，将递归函数转换为迭代函数可以节省大量宝贵的内存。
这是一个试图吃掉你所有 RAM 的错误。您忘记了递归中的基本情况或错误地调用了相同的函数。我们都完成了至少 2 次。
不一定有多少调用会导致溢出——这取决于每个单独的调用在堆栈帧上占用了多少内存。每个函数调用都会用完堆栈内存，直到调用 returns。堆栈内存是静态分配的——您不能在运行时更改它（在一个理智的世界中）。这是幕后的后进先出 (LIFO) 数据结构。
它并没有阻止它，它只是改变了对
grow_Wolff_cluster的调用次数以溢出堆栈内存。在 32 位系统上，从函数中删除neighbor会使对grow_Wolff_cluster的调用减少 4 个字节。当你乘以数十万时，它加起来很快。
我建议您了解更多有关堆栈如何为您工作的信息。 Here's a good resource over on the software engineering stack exchange. And another here on stack overflow（兴奋！）
I want to know that is this normal?
是的。筹码量只有这么多。
In the code below, removing local variable neighbor can prevent from stack overflow?
没有。即使没有变量和 return 值，函数调用本身也必须存储在堆栈中，以便最终可以展开堆栈。
例如...
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 标准定义的，而是由实现定义的。 C 标准定义了一种具有无限堆栈的语言 space（以及其他资源），但确实有一节关于如何允许实现施加限制。
通常首先造成错误的是操作系统。 OS 并不关心你调用了多少次，而是关心堆栈的 总大小 。栈由栈帧组成，每个函数调用一个。通常堆栈帧由以下五种东西的某种组合组成（作为近似值；不同系统的细节可能有很大差异）：
- 函数调用的参数（在这种情况下可能实际上不在这里；它们可能在寄存器中，尽管这实际上并没有用递归购买任何东西）。
- 函数调用的return地址（本例为
for循环中++i指令的地址）。 - 上一个堆栈帧开始的基指针
- 局部变量（至少那些不进入寄存器的变量）
- 调用者在进行新的函数调用时想要保存的任何寄存器，因此被调用的函数不会覆盖它们（一些寄存器可能会被调用者保存，但它对堆栈大小并不特别重要分析）。这就是为什么在这种情况下在寄存器中传递参数没有多大帮助；他们迟早会进入堆栈。
因为其中一些（特别是 1.、4. 和 5.）的大小可能相差很大，所以很难估计平均堆栈帧有多大，尽管在这种情况下更容易因为递归。不同的系统也有不同的堆栈大小；目前看起来默认情况下我可以有 8 MiB 的堆栈，但嵌入式系统可能会少很多。
这也解释了为什么删除局部变量会为您提供更多可用的函数调用；您减少了 500,000 个堆栈帧中每个堆栈帧的大小。
如果您想增加可用的堆栈数量 space，请查看 setrlimit(2) function（在 Linux 上与 OP 类似；在其他系统上可能有所不同）。不过，首先，您可能想尝试调试和重构以确保您需要所有堆栈 space.
这是一个简单的 c# 函数，它会告诉你在堆栈溢出之前你的计算机可以进行多少次迭代（作为参考，我有 运行 最多 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);
}
在这种简单的情况下，条件检查："if (plngStack > plngMax)" 可以删除， 但是如果你有一个真正的递归函数，这个检查将帮助你定位问题。