在堆栈已满之前,C/C++中的最大递归函数调用会产生分段错误吗？

Question

我在做一个问题,我用一个递归函数来创建一个分段树.对于较大的值,它开始给出分段错误.所以我想之前可能是因为数组索引值超出了界限但后来我认为可能是因为程序堆栈太大了.我编写此代码来计算系统给出seg-fault之前允许的最大递归调用次数.

#include<iostream>
using namespace std; 
void recur(long long int);
int main()
{
  recur(0);
  return 0;
}
void recur(long long int v)
{
  v++;
  cout<<v<<endl;
  recur(v);

}

在运行上面的代码之后,我得到v的值为261926和261893和261816,然后才得到分段错误并且所有值都接近这些.

现在我知道这将取决于机器到机器,以及被调用的函数堆栈的大小,但是有人可以解释如何保护安全免受seg-fault的基础知识以及可以记住的软限制是什么.

Answer 1

有(AFAIK)没有完善的限制.(我从Linux桌面的角度回答).

在台式机,笔记本电脑上,2015年默认堆栈大小为几兆字节.在Linux上,你可以使用setrlimit(2)来改变它(到一个合理的数字,不要指望这些天能够将它设置为千兆字节) -你可以使用getrlimit(2)或解析/proc/self/limits(参见proc(5))来查询它.在嵌入式微控制器上 - 或在Linux内核中 - 整个堆栈可能会受到更多限制(总共几千字节).

使用pthread_create(3)创建线程时,可以使用显式pthread_attr_t并使用pthread_attr_setstack(3)来设置堆栈空间.

顺便说一句,在最近的GCC中,您可以使用拆分堆栈编译所有软件(包括标准C库)(因此传递给或)-fsplit-stackgccg++

最后你的例子是一个尾调用,GCC可以优化它(用参数跳转).我查了一下,如果你有编译g++ -O2(使用GCC 4.9.2在Linux/x86-64的/ Debian的)递归会变成一个真正的循环,并没有堆栈分配将无限期地增长(近4000万的程序运行调用recur的分钟,然后我打断它)在更好的语言如Scheme或Ocaml中,保证尾调用确实是迭代编译的(然后尾递归调用成为通常 - 甚至是唯一的循环结构).

Cyber​​Spok的评论过多(暗示避免递归).递归非常有用,但你应该将它们限制在一个合理的深度(例如几千),你应该注意调用堆栈上的调用帧很小(每个小于一千字节),所以实际上分配和释放大部分C堆中的数据.GCC -fstack-usage选项对报告每个已编译函数的堆栈使用非常有用.看到这个和那个答案.

请注意,continuation传递样式是将递归转换为迭代的规范方法(然后使用动态分配的闭包交换堆栈帧).

一些聪明的算法用花式修改迭代替换递归,例如Deutche-Shorr-Waite图形标记算法.

Answer 2

您可以执行的递归级别数取决于调用堆栈的大小以及放置在此类堆栈上的局部变量和参数的大小。除了“如何编写代码”之外，就像其他许多与内存相关的事情一样，这很大程度上取决于您所运行的系统，所使用的编译器，优化级别[1]等。我正在研究的某些嵌入式系统，堆栈将是几百个字节，我的第一台家用计算机具有256字节的堆栈，而现代台式机具有兆字节的堆栈（您可以对其进行调整，但最终会用完）

进行无限深度的递归不是一个好主意，您应该考虑将代码更改为“不会这样做”。您需要了解算法并了解递归的深度，以及在系统中是否可以接受。不幸的是，在堆栈耗尽时，任何人都无法做任何事情（最好是您的程序崩溃，最坏的情况下不会崩溃，而是导致ELSE出错，例如其他应用程序的堆栈或堆弄乱了！ ）

在台式机上，我认为递归深度为几百到几千，但不超过此深度是可以接受的，也就是说，如果每次调用都使用少量堆栈，则每次调用都使用如果堆栈空间超过千字节，则应该进一步限制调用级别，或者减少对堆栈空间的需求。

如果您需要更多的递归深度，则需要重新安排代码-例如，使用软件堆栈存储状态以及代码本身中的循环。

[1]在您发布的代码上使用g ++ -O2，我得到了5000万并计数，我希望如果我将其保留足够长的时间，它将以零开始重新启动，因为它将一直持续下去-这是因为g ++检测到该递归可以转换为循环，然后执行此操作。用-O0或-O1编译的同一程序确实在200000处停止。使用clang ++ -O1可以继续运行。当我完成其余代码的编写时，使用clang编译的代码仍在运行，重复次数为1.85亿。