13

Is there a way to know in c++ the maximum recursion depth without explicitly calling the recursion until it crashes?

I've seen that's limited by the size of the stack. Maybe it can be useful to find at a specific recursion level the amount of free space in the stack. Is it possible?

Flame_Phoenix
  • 16,489
  • 37
  • 131
  • 266
Jepessen
  • 11,744
  • 14
  • 82
  • 149
  • 1
    There's nothing in `C++` that defines the maximum depth. The maximum depth is dependent on CPU architecture, compiler-specific implementation details, and the actual function being recursed (along with child functions it calls). Like any other problem, sure, if you know all the parameters you can determine a solution.... but in this case it's probably much easier to just do the explicit call and see what you get. – mah Mar 01 '16 at 16:48
  • 1
    Though there is a paragraph in `[temp.inst]` that says there is an implementation defined quantity. – NathanOliver Mar 01 '16 at 16:51
  • 1
    So if there a way to check the free stack size in order to stop the recursion when it's below a specified limit? – Jepessen Mar 01 '16 at 16:52
  • 1
    I'm voting to reopen this question, because it's not the same as the one identified as a duplicate. This is not asking why there's a limit, or if C++ defines the limit - it asks if there's a mechanism for estimating the limit in the currently running program. – Mark Ransom Mar 01 '16 at 16:53
  • I wonder if the information about the current remaining stack size is of any use, or what problem could be solved, or why is this information needed at all. On the other hand, compilers are good in tail call optimization and transforming recursion. – knivil Mar 01 '16 at 16:56
  • because in another thread http://stackoverflow.com/questions/16126241/limit-recursive-calls-in-c-about-5000 they say that call number limit depends on the size of the stack. So i can put an end to the limit of the recursion without crashing the program if I set a limit to the minimum free stack size. – Jepessen Mar 01 '16 at 17:01
  • 4
    Any answer is going to be platform and compiler specific so you should specify those in your question. – Mark B Mar 01 '16 at 17:05
  • Maybe this might help you to at least figure out how large your stack is at a certain timepoint: http://stackoverflow.com/a/53836/4181011 – Simon Kraemer Mar 01 '16 at 17:07
  • 3
    @Jepessen: That is the wrong solution to tackle whatever your problem might be. – knivil Mar 01 '16 at 17:18
  • Probably you're right, but it's not a bad idea to stop recursion at some point and give an error, instead that see the program that crashes. I'll put some other control in production code, but curiosity remains... – Jepessen Mar 01 '16 at 18:04

2 Answers2

2

The only thing that I can think of right now is to use getrlimit to get the maximum size of the stack dedicated to your process. Next thing to do is find a way of getting the currently used stack size. I thought that getrusage is the way to go but after looking at the man-page and a couple of posts on SO it seems that it no longer supports this particular feature. So you have to find another way. I do believe that Valgrind also reports the stack usage so looking into its source code and documentation may prove useful.

Once you are able to get the current stack size you can measure

  • its initial state before you start the recursion (so that you can exclude this from your calculations since it doesn't have anything to do with the recursion itself)

  • its change for a single iteration

Excluding the initial stack allocation along with using the total stack size and the allocation required for a single recursion step you should be able to approximate the number of recursions you can have for the given system. I'm not sure if it will work and also such measurements even if accurate are highly dependant on the system you are using (after all stack is closely related to the amount of virtual memory a process can have).

rbaleksandar
  • 8,713
  • 7
  • 76
  • 161
2

The maximum recursion depth depends on the amount of memory used by the function(s), the amount of memory on your platform and the limits (if any) by the OS or the compiler.

In a recursive call, memory is occupied by:

  • The overhead of a function call
  • The memory occupied by the parameters passed.
  • The memory occupied by local variables

A recursive function with no parameters and no local variables will have a higher possible depth (number of recursive calls) than a function that passes a lot of large objects and occupies a lot of local variables.

So, the answer to your question is: the maximum number of recursive calls depends on the amount of memory occupied by a recursive call, the amount of memory on the system and any limits imposed by the compiler or operating system. Different recursive functions occupy different amounts of memory.

If you know all these items, then you can calculate the maximum number of possible recursions.

Thomas Matthews
  • 56,849
  • 17
  • 98
  • 154