Find maximum recursion depth

11
votes

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?

2
c++recursion
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
Though there is a paragraph in [temp.inst] that says there is an implementation defined quantity. - NathanOliver
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
Any answer is going to be platform and compiler specific so you should specify those in your question. - Mark B
@Jepessen: That is the wrong solution to tackle whatever your problem might be. - knivil

2 Answers

2
votes

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).

2
votes

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.