froglogic / All / 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. 🙂

Tags

I would just use a goto. So whenever you want to return, instead of remembering your counter and and then having a return statement, just jump to a label at the end and after that label is the counter decrement.

Well, you could use a little macro, and do something like that (it is less elegant, but it does work) :

class RecursionCounter
{
public:
inline RecursionCounter(int& cnt_) : cnt(cnt_) { ++cnt; }
inline ~RecursionCounter() { –cnt; }
private:
int& cnt;
};

#define RECURSION_COUNTER_IMPL(mangled, name) static int mangled = 0; RecursionCounter name(mangled)
#define RECURSION_COUNTER(name) RECURSION_COUNTER_IMPL(name ## _counter, name)

int f(int i, int acc)
{
RECURSION_COUNTER(depth);

if (i > 0)
return f(i – 1, acc + 1);

return acc;
}

Since on every recursive call you create a new stackframe you could use something like that:
void f(int cnt) {
printf( “Recursion depth is: %d”, cnt);
f(++cnt);
}

But I don’t know if that solves your problem. It all depends on the context.

wouldn’t it be easier to just do

f(int depth)
{
depth++; // do this as the first line of the function

f(depth);
}

@anonymous:
The thing is that there are more ways to return from the function (in particular, the function is using some API which can throw exceptions – which I deliberately do not catch) than simply calling ‘return’.

@sdefresne:
Maybe I’m overlooking something but instead of saying ‘RecursionCounter<0>‘ and ‘RecursionCounter<1>‘, your macro lets me write ‘RecursionCounter‘ and ‘RecursionCounter‘, no? I can use something else than an integer as the ‘name’. That’s not too bad indeed. However, I’d like to get rid of this entirely. 🙂

@robewald:
You are right. However, I was touching a function with a fixed signature, so I could not add an argument to the function to transport the recursion depth counter value. Another possible problem I see is that instead of having to remember to decrement the recursion depth for every return path from the function, one has to remember to increment the recursion depth counter for every recursive invocation.

@Casper Boemann:
Only if I could live with making this counter part of the public API (this is a public function), which I cannot. For esthetic and practical reasons. 🙂

To the guy with the “goto solution”: The biggest problem with that idea is that it is not exception safe. If an excpetion is thrown and not caught within the function being tracked, the state of the counter will get out of sync with reality. Look up the idea “resource acquisition is initialization” for more info.

Getting back to the other solutions: The problem with static variables is that you only have one of them per function. What happens in a multi-threaded environment?

robewald has the best idea. I would modify his solution to preserve f()’s interface like this: f() ( int depth=0; f_impl(++depth); }

What is wrong with try … finally ? It will use much less code. They are made for this exact purpose.

recursiondepth++;
try {
blabla …
} finally {
recursiondepth–;
}

private:
f(int depth)
{
depth++; // do this as the first line of the function

f(depth);
}

public:
f()
{
f(0);
}

i think, a dynamic system is easier to implement than your template based idea.
i would do it this way:
class RecursionCounter{
public:
RecursionCounter(void* ptr):m_ptr(ptr){m_map[m_ptr]++;}
~RecursionCounter(){m_map[m_ptr]–;}
operator int() {return m_map[m_ptr];}
private:
static std::map m_map;
void* m_ptr;
};

std::map RecursionCounter::m_map = std::map();

void myfunction()
{
RecursionCounter((void*)&myfunction);

}

i think, a dynamic system is easier to implement than your template based idea.
i would do it this way:
class RecursionCounter{
public:
RecursionCounter(void* ptr):m_ptr(ptr){m_map[m_ptr]++;}
~RecursionCounter(){m_map[m_ptr]–;}
operator int() {return m_map[m_ptr];}
private:
static std::map m_map;
void* m_ptr;
};

std::map RecursionCounter::m_map = std::map();

void myfunction()
{
RecursionCounter((void*)&myfunction);

}

First of all I must say that I’m amazed how many different ways people think up to solve such a simple problem. 🙂

Regarding the ‘pass recursion count as function argument to internal implementation function’ (what Adam and robewald basically said): yes I considered using a second function. However, this would mean that I would have to introduce a second function for each function which needs a recursion counter; which, in my case, is a lot more lines of code than simply putting a ‘RecursionCounter recursionDepth;’ at the top of the function body.

You’re right though that I did not care about thread safety. That’s because I don’t use any threads at all in this code – but thank you for pointing this out!

I would use something like:

class RecursionCounter
{
public:
inline RecursionCounter()
inline ~RecursionCounter()
inline operator int() const { return cnts[const_cast(this)]; }
private:
static std::map cnts;
};

where the constructor would take care of adding a new entry for ‘this’ and setting its counter to 1, or simply incrementing the counter, Same thing (but with the decrementing , and the erasing if needed) for the destructor. (Sorry if I don’t write them down, I’m in hurry…)

I’m not sure whether I should edit the original article in case I want to augment it or whether posting a comment to my own blog is okay. I’ll go for the latter for now:

after talking with my colleague about this, we found that both of the two ‘popular’ solutions have tricky problems:

1.) The ‘Hide static int in class’ solution (what I came up with in my original post) will easily break if the function is a member function. Consider this:

``` class C { public: void f() { RecursionCounter<0> recursionDepth; printf( "Recursion depth: %dn", recursionDepth ); } }; ```

Now, this will break when invoking C::f on two different objects. If this member function was a static function (a ‘class function’) then everything would be right – alas, it’s not.

2.) The other suggestion to pass the recursion depth count as a function argument does not work well when dealing with indirect recursion. Imagine that ‘f’ does not call itself but instead calls ‘g’ – which in turn calls ‘f’. In order to implement this solution, both ‘f’ and ‘g’ would have to have their argument list augmented with the recursion counter. Ugly.

In the absense of threads, I think the prize goes to sdefresne’s macro solution.

The problem with the map based solutions is that you have to lookup your void* at each call, that could get expensive depending on the size of the task and how many functions you are counting. Even removing the entry when the counter goes back to 0 will not be enough if f() is something like an alpha-beta search.

“1.) The ‘Hide static int in class’ solution (what I came up with in my original post) will easily break if the function is a member function. ”
if you use my idea with the pointer as the key in a map, you can easily workaround the member function problem, by adding the this-pointer to the function-pointer. (the problem with an overflow can be solved by converting the pointers to longs.)
“2.) The other suggestion to pass the recursion depth count as a function argument does not work well when dealing with indirect recursion.”
if you use a function pointer to identify your function, there is no problem with this.

Here’s another idea — if you are using libc, you can simply use the “backtrace” and “backtrace_symbols” functions to get a stack list then simply count the number of occurrences of your function name in the result. You will need to compile with -rdynamic. I haven’t tested this idea, but there’s a linux journal article on using these .

Oops. The article I mentioned is here. Sorry ’bout that.

I agree, the f_impl() solution is unworkable if f calls g calls f….

But your point about member functions is lost on me. It seems to me that no matter where you hide your static variable, you are only going to have one of them per member function. But this would only matter if you had recursive objects, i.e a.f() calls b.f() calls a.f()…. I think this would be a rare case.

If this rare case matters to you then you need some sort of support for reflection. then you could look up the object and the member function (and context?) and update that specific counter.

@Adam i thought this stuff will only be used in a debug enviroment, this why i thought performance wasn’t that critical.

“The problem with the map based solutions is that you have to lookup your void* at each call, that could get expensive depending on the size of the task and how many functions you are counting.”
if this isn’t used in an embedded system, you will never get so many recursive functions, that memory size could get a problem. we are talking about less than 10bytes per function. you will need more memory to save all your breakpoints…
the execution-time isn’t that worse, since the function-pointer is known at compiletime, so there is no lookup needed. it will only pass an int as ctor argument.

@Gregor

The article says: “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.”

I assumed the features were application features and therefore this was not a debug only discussion.

I was thinking more of speed cost than memory cost. That’s why I used alpha-beta serach as my example.

It would perhaps be interesting to know why the OP thinks he needs to know where he is in the call stack in order to add his feature.

PS. I hate the captcha. It takes me about 3 tries to post.

You could try using Boost.Fusion’s compile-time map using

class MY_F_COUNTER;
class MY_G_COUNTER;

as keys to get at the run-time counters.

what about passing a ref on the counter to the class (int’s just here to increment the value;

class incrementor {
public:
incrementor(int& i) : m_i(i) {m_i++;}
~incrementor() {m_i–;}
int& m_i;
}

and the function is

void f() {
static int recursionDepth=0;
incrementor incr(recursionDepth);

printf( “Recursion depth: %dn”, recursionDepth );
}

With some spicy invariants added 🙂

struct algo
{
int rcount;
algo() : rcount(0) {}
// Recursive alorithm entrypoint
// Assures algoriithm isn’t started yet.
f() {
assert( rcount == 0 );
f_intern();
assert( rcount == 0 );
}
private:
struct reclvl {
reclvl(int& _r) : r(++_r) {}
~reclvl() { –r; }
int level() const { return r; }
private:
int& r;
};
f_intern()
{
reclvl( a_rcount );

do_stuff().

}
};

I would make use of C99’s __func__ , or __PRETTY_FUNCTION__ (GCC only, but how useful) from a macro, something like:

class RecursionCounter
{
public:
inline RecursionCounter(string funcname) { counter[funcname]++; }

private:
static std::map counter;
};

#define RECURSION_COUNTER RecursionCounter _counter(__func__)

void f()
{
RECURSION_COUNTER;

}

Personally I always use a different solution (of course it adds to stack bloat, but whatever) but it has served me well in programming competitions. Also the compiler wont catch it if you make a call to f without using the parameter recursionDepth, which can lead to annoying bugs. However default parameters never bit in this case, because I pretty much always have a depth in there.

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

printf( “Recursion depth is: %dn”, recursionDepth );
// Lots of code here; for each return path, don’t forget
// to decrement recursionDepth!

}

better late than never: what about making your template argument a void*, and use the function itself as the template argument. You would get a separate object for each function, clashing only if the two functions are … the same.
Maybe this would work with a char* template argument and then using some predefined macro to make a unique string for each function, like __FILE__ #__LINE__

In these cases, thread-safety would have to be implemented in the RecursionCounter itself.

I was a supposed to take up Java Script as an extra course for the company that I was applying to did not find my resume that impressive. Its a good thing I did not continue for there are a lot of other way to learn about programming languages, especially on the web.

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. tava tea