How can I find the depth of a recursive function in C++

Question

How can I find the current depth inside a recursive function in C++ without passing in the previous level? i.e. is it possible to know how many times the function was called without using a parameter to keep track of the level and passing that number in as a parameter each time the function is called?

For example my recursive function looks like this:

DoSomething(int level)
{
  print level;
  if (level > 10)
    return;
  DoSomething(++level);
}

main
{
  DoSomething(0);
}

Answer 1

You can use a local static variable, if you don't care about thread-safety.

Although, this will only give you a proper count the first time you run your recursive routine. A better technique would be a RAII guard-type class which contains an internal static variable. At the start of the recursive routine, construct the guard class. The constructor would increment the internal static variable, and the destructor would decrement it. This way, when you create a new stack-frame the counter increments by one, and when you return from each stack-frame the counter would decrement by one.

struct recursion_guard
{
    recursion_guard() { ++counter; }

    ~recursion_guard() { --counter; }

    static int counter;
};

int recursion_guard::counter = 0;

void recurse(int x)
{
    recursion_guard rg;
    if (x > 10) return;
    recurse(x + 1);
}

int main()
{
    recurse(0);
    recurse(0);
}

Note however, that this is still not thread-safe. If you need thread-safety, you can replace the static-storage variable with a thread-local-storage variable, either using boost::thread_specific_ptr or the C++0x thread local facilities.

Answer 2

You could use a static variable in the function...

void recursive()
{
 static int calls = 0;
 calls++;
 recursive();
}

Of course, this will keep counting when you start a new originating call....

Answer 3

Building on the answer already given by JoshD:

void recursive() 
{ 
    static int calls = 0;
    static int max_calls = 0;
    calls++;
    if (calls > max_calls)
        max_calls = calls;

    recursive();

    calls--;
}

This resets the counter after the recursive function is complete, but still tracks the maximum depth of the recursion.

I wouldn't use static variables like this for anything but a quick test, to be deleted soon after. If you really need to track this on an ongoing basis there are better methods.

Answer 4

convert level to an instance variable of a new object (typically a template) capable of containing the arguments and (possibly) the function. then you can reuse the recursion accumulator interface.

Answer 5

You can also try using a global variable to log the depth.

var depth = 0;

DoSomething()
{
  print ++depth;
  if (depth > 10)
    return;
  DoSomething();
}

main
{
  DoSomething(0);
}

Answer 6

You could also pass in the level as a template parameter, if it can be determined at compile-time. You could also use a function object. This is by far and away the best option - less hassle, and static variables should be avoided wherever possible.

struct DoSomething {
    DoSomething() {
        calls = 0;
    }
    void operator()() {
        std::cout << calls;
        calls++;
        if (calls < 10)
            return operator()();
        return;
    }
    int calls;
};

int main() {
    DoSomething()(); // note the double ().
    std::cin.get();
}

Answer 7

If you want it to be re-entrant and thread-safe, why not:

void rec(int &level)  // reference to your level var
{
   // do work

   rec(++level); // go down one level
}

main()
{
   //and you call it like
   int level=0;
   rec(level);

   cout<<level<<" levels."<<endl;
}

No static/global variables to mess up threading and you can use different variables for different recursive chains for re-entrancy issues.