Geek asks and answers

What is the order of magnitude of the maximum number of recursive calls in C ++?

I have a recursive function that calls itself so many times with certain inputs, which is what it should do. I know that my function does not endlessly loop - it just reaches a certain number of calls and overflows. I want to know if this is a problem, if there is too much memory on the stack or just a normal limit on the number of calls. Obviously, it is very difficult to say a certain number of calls, which is the maximum, but can someone give me a rough estimate of the order of magnitude? Is it in the thousands? Hundreds? Millions?

+3
source share
5 answers

It completely depends on how much information you use on the stack. However, the default stack for Windows is 1 MB, and the default stack for Unix is ​​8 MB. Just a call can include pressing a few 32-bit registers and a return address, say, so you can see maybe 20bytes a call that would put a maximum of about 50k on Windows and 400k on Unix for an empty function.

Of course, as far as I know, you can resize the stack.

+2
source

So, as you may have guessed, the problem is overflowing the stack (of the same name). For each call, you need to create a new stack stack by inserting new information on the stack; the stack size is fixed and eventually ends.

? - . Microsoft ( VS2010) 1 , "/F" (. '03, ).

, . , ( ), . , , ( ). , . , , , 256 , 1M 4096 - ..

, Tail Call Optimization, . MSVC . , , "/F" ( ) .

+3

. , . , .

, valgrind .

0

, , , .

, . , , , , , , 20 . , .

, , , .

; , , .

, , - , , , ( ), , ( , , , ) - .

And, as others have said, you can increase the size of the allowed stack, but this will probably have limited use - and this is one more thing that you will need to do before launching your program. It can also consume resources and interfere with other processes in the system (restrictions are imposed for some reason).

Changing the algorithm to avoid recursion may be an opportunity, but again, we don’t have enough information to talk a lot about it.

0
source

More articles:


All Articles