在堆栈已满并给出分段错误之前，C/C++ 中的最大递归函数调用？

Question

我在做一道题，我用递归函数创建了一个线段树。对于较大的值，它开始给出分段错误。所以我之前认为可能是因为数组索引值越界，但后来我认为可能是因为程序堆栈太大。我写这段代码来计算在系统给出段错误之前允许的最大递归调用次数。

#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，并且所有值都接近这些。

现在我知道这将取决于机器与机器之间的关系，以及被调用函数的堆栈大小，但是有人可以解释一下如何避免段错误的基础知识以及什么是软限制大家可以牢记。

Answer 1

（据我所知）没有明确的限制。（我是从 Linux 桌面角度回答的）。

在台式机和笔记本电脑上，2015 年的默认堆栈大小为几兆字节。在 Linux 上，您可以使用 setrlimit(2) to change it (to a reasonable figure, don't expect to be able to set it to a gigabyte these days) - and you could use getrlimit(2) or parse /proc/self/limits (see proc(5)) 来查询它。在嵌入式微控制器上 - 或者在 Linux 内核中 - ，整个堆栈可能更加有限（总共几千字节）。

创建线程时使用pthread_create(3) you could use an explicit pthread_attr_t and use pthread_attr_setstack(3)设置堆栈space。

顺便说一句，最近 GCC, you might compile all your software (including the standard C library) with split stacks（因此将 -fsplit-stack 传递给 gcc 或 g++）

最后你的例子是 tail call，GCC 可以优化它（变成带参数的跳转）。我检查过如果你用 g++ -O2 编译（在 Linux/x86-64/Debian 上使用 GCC 4.9.2），递归将被转换成一个真正的循环，并且没有堆栈分配会无限增长（你的程序运行一分钟内对 recur 进行了将近 4000 万次调用，然后我打断了它）在 Scheme 或 Ocaml 等更好的语言中，可以保证尾调用确实是迭代编译的（然后尾递归调用通常 - 甚至是仅循环结构）。

CyberSpok is excessive in his comment (hinting to avoid recursions). Recursions are very useful, but you should limit them to a reasonable depth (e.g. a few thousands), and you should take care that call frames on the call stack are small (less than a kilobyte each), so practically allocate and deallocate most of the data in the C heap. The GCC -fstack-usage options is really useful for reporting stack usage of every compiled function. See this and that 个答案。

注意 continuation passing style is a canonical way to transform recursions into iterations (then you trade stack frames with dynamically allocated closures).

一些聪明的算法用花哨的修改迭代代替递归，例如Deutche-Shorr-Waite graph marking algorithm.

Answer 2

您可以执行的递归级别数取决于调用堆栈大小以及放置在此类堆栈上的局部变量和参数的大小。除了 "how the code is written"，就像许多其他内存相关的东西一样，这在很大程度上取决于您运行正在使用的系统、您使用的编译器、优化级别 [1]，等等.我工作过的一些嵌入式系统，堆栈有几百字节，我的第一台家用电脑有 256 字节的堆栈，而现代台式机有数兆字节的堆栈（你可以调整它，但最终你会运行出)

无限深度递归不是一个好主意，您应该考虑将代码更改为 "it doesn't do that"。您需要了解算法并了解它将递归到什么深度，以及这在您的系统中是否可以接受。不幸的是，在 stack 运行s out 的时候，任何人都无能为力（充其量你的程序崩溃，最坏的情况下它不会崩溃，而是导致其他地方出错，例如其他一些堆栈或堆应用程序搞砸了！）

在台式机上，我认为递归深度为几百到几千是可以接受的，但不要超过这个——也就是说，如果你在每次调用中使用的堆栈很少——如果每个调用都用完了千字节的堆栈，您应该进一步限制调用级别，或者减少对堆栈的需求-space。

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

[1] 在您发布的代码上使用 g++ -O2，我达到了 5000 万并且还在增加，我希望如果我保留它足够长的时间，它会从零重新启动，因为它会一直运行 - 这是因为 g++ 检测到这个递归可以转换成一个循环，然后就这样做了。使用 -O0 或 -O1 编译的同一个程序确实在 200000 多一点时停止。使用 clang++ -O1 它会继续运行。当我写完其余代码时，clang 编译的代码仍然运行ning，为 1.85 亿 "recursions".

Answer 3

对于基于 Linux 的应用程序，我们可以使用 getrlimit 和 setrlimit API 来了解各种内核资源限制，如核心文件大小、cpu 时间、堆栈大小、不错的值，最大。不。进程等 'RLIMIT_STACK' 是 linux 内核中定义的堆栈的资源名称。下面是检索堆栈大小的简单程序：

#include <iostream>
#include <sys/time.h>
#include <sys/resource.h>
#include <errno.h>
using namespace std;

int main()
{
   struct rlimit sl;
   int returnVal = getrlimit(RLIMIT_STACK, &sl);
   if (returnVal == -1)
   {
      cout << "Error. errno: " << errno << endl;
   }
   else if (returnVal == 0)
   {
      cout << "stackLimit soft - max : " << sl.rlim_cur << " - " << sl.rlim_max << endl;
   }
}

在堆栈已满并给出分段错误之前，C/C++ 中的最大递归函数调用？

Maximum recursive function calls in C/C++ before stack is full and gives a segmentation fault?

c++

recursion

segmentation-fault