且构网

分享程序员开发的那些事...
且构网 - 分享程序员编程开发的那些事

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

更新时间:2021-10-20 01:00:59

您可以执行的递归级别数取决于调用堆栈的大小以及放置在此类堆栈上的局部变量和参数的大小.除了如何编写代码"之外,就像许多其他与内存相关的事情一样,这在很大程度上取决于您运行的系统、您使用的编译器、优化级别 [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".