在堆栈已满并给出分段错误之前，C/C++ 中的最大递归函数调用? [英] Maximum recursive function calls in C/C++ before stack is full and gives a segmentation fault?

问题描述

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

I was doing a question where I used a recursive function to create a segment tree. For larger values it started giving segmentation fault. So I thought before it might be because of array index value out of bound but later I thought it might be because of program stack going too big. I wrote this code to count what is the maximum number of recursive calls allowed before the system give 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，并且所有值都接近这些值.

After running the above code I got value of v to be 261926 and 261893 and 261816 before getting segmentation fault and all values were close to these.

现在我知道这将取决于机器到机器，以及被调用函数的堆栈大小，但有人可以解释如何防止段错误的基础知识以及可以使用的软限制是什么记住.

Now I know that this would depend on machine to machine, and the size of the stack of the function being called but can someone explain the basics of how to keep safe from seg-faults and what is a soft limit that one can keep in mind.

推荐答案

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

The number of recursion levels you can do depends on the call-stack size combined with the size of local variables and arguments that are placed on such a stack. Aside from "how the code is written", just like many other memory related things, this is very much dependent on the system you're running on, what compiler you are using, optimisation level [1], and so on. Some embedded systems I've worked on, the stack would be a few hundred bytes, my first home computer had 256 bytes of stack, where modern desktops have megabytes of stack (and you can adjust it, but eventually you will run out)

以无限深度进行递归不是一个好主意，您应该考虑将代码更改为它不会那样做".您需要了解算法并了解它将递归到什么深度，以及这在您的系统中是否可以接受.不幸的是，当堆栈用完时，任何人都无能为力(最好的情况是您的程序崩溃，最坏的情况不会，而是会导致 ELSE 出错，例如其他应用程序的堆栈或堆被弄乱了！)

Doing recursion at unlimited depth is not a good idea, and you should look at changing your code to so that "it doesn't do that". You need to understand the algorithm and understand to what depth it will recurse, and whether that is acceptable in your system. There is unfortunately nothing anyone can do at the time stack runs out (at best your program crashes, at worst it doesn't, but instead causes something ELSE to go wrong, such as the stack or heap of some other application gets messed up!)

在台式机上，我认为递归深度从几百到几千是可以接受的，但不会比这更多——也就是说，如果你在每次调用中使用的堆栈很少——如果每个call 正在使用千字节的堆栈，您应该进一步限制调用级别，或减少对堆栈空间的需求.

On a desktop machine, I'd think it's acceptable to have a recursion depth of a hew hundred to some thousands, but not much more than this - and that is if you have small usage of stack in each call - if each call is using up kilobytes of stack, you should limit the call level even further, or reduce the need for stack-space.

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

If you need to have more recursion depth than that, you need to re-arrange the code - for example using a software stack to store the state, and a loop in the code itself.

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

[1] Using g++ -O2 on your posted code, I got to 50 million and counting, and I expect if I leave it long enough, it will restart at zero because it keeps going forever - this since g++ detects that this recursion can be converted into a loop, and does that. Same program compiled with -O0 or -O1 does indeed stop at a little over 200000. With clang++ -O1 it just keeps going. The clang-compiled code is still running as I finished writing the rest of the code, at 185 million "recursions".

这篇关于在堆栈已满并给出分段错误之前，C/C++ 中的最大递归函数调用?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！