Recursion Depth Counting

Recursion Depth Counting

I’ve been touching this function which happens to call itself recursively and found that in order to add some feature, I needed to know how deeply I recursed into the function already. Null problemo, I thought:

void f()
{
    static int recursionDepth = 0;
    ++recursionDepth;

    printf( "Recursion depth is: %d\n", recursionDepth );
    // Lots of code here; for each return path, don't forget
    // to decrement recursionDepth!

    --recursionDepth;
}

Very little code. Very easy to understand. Very error prone. And – in case you have to keep track of the recursion depth in other places, very repetitive.

The #1 problem is that it’s very easy to forget to decrement the recursionDepth counter variable in case you return from the function somewhere else than the end of it. I happen to do that very very often, and I know myself well enough to know that I’ll probably forget to care about the recursionDepth variable if I add some new code (with a new return statement) in the middle of that function.

Luckily, I found a pretty easy solution to this though.

My first idea was to use a dedicated ‘RecursionDepthCounter’ class, like this:

class RecursionCounter
{
public:
    inline RecursionCounter() { ++cnt; }
    inline ~RecursionCounter() { --cnt; }
    inline operator int() const { return cnt; }
private:
    static int cnt;
};
int RecursionCounter::cnt = 0;

Now I can simplify my function f() a lot already:

void f()
{
    RecursionCounter recursionDepth;

    printf( "Recursion depth is: %d\n", recursionDepth );
    // Lots of code here; don't need to care about 'return' statements
}

The trick is to rely on the RecursionCounter constructor to increment the (internal) static counter variable, and the destructor to decrement it again. C++ will call the destructor for us automatically, no matter how and when we leave the function. For a little sugar, we add a little implicit conversion operator to int so that we can use RecursionCounter objects just like integers.

Not bad, I thought. So I could go through my code and replace the situations where I kept track of the recursion depth with this little piece of code, and it all looked innocent, and simple, and easy. And it didn’t work.

The problem is that when using more than one RecursionDepth object in your code (for instance, because you have two functions within which you want to keep track of the recursion depth), those objects will share the internal ‘cnt’ counter variable. Not so nice. What we really want is a static counter *per function*. I found a simple trick which solves this problem, too:

template <int>
class RecursionCounter
{
public:
    inline RecursionCounter() { ++cnt; }
    inline ~RecursionCounter() { --cnt; }
    inline operator int() const { return cnt; }
private:
    static int cnt;
};
template <int num>
int RecursionCounter<num>::cnt = 0;

Looks almost like the old class I just presented. Almost; the difference is that this isn’t a class, but only a template for a whole
group of classes. The template argument is not used by the class at all, it’s only used to make the compiler generate different
classes as I need them. Now, if I want to keep track of the recursion depth in two functions, I can do this:

void f()
{
    RecursionCounter<0> recursionDepth;

    printf( "Recursion depth in f is: %d\n", recursionDepth );
}

void g()
{
    RecursionCounter<1> recursionDepth;

    printf( "Recursion depth in g is: %d\n", recursionDepth );
}

Now I’m really using two different recursion counter classes (RecursionCounter<0> and RecursionCounter<1>) and thus two different static cnt counter variables. Very nice. 🙂

The only thing about this which annoys me a bit is that I have to make sure not to use any integer as the template argument which is in use already. If anybody knows a nice solution to this (I have a gut feeling that doing the ‘recursive template enum counter’ trick will work), please let me know. 🙂