11

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);
}
1
  • 2
    you might want to have a look at this discussion. The bottom line is that there might be a compiler/platform specific way to get the backtrace and use that...but it's obviously very compiler/platform specific and probably susceptible to things like inlining. In any event, might be worth a look. Commented Oct 29, 2010 at 23:37

8 Answers 8

14

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.

5

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

1
  • Yes that is a problem. How would I reset calls? Commented Oct 29, 2010 at 22:37
4

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.

2
  • 1
    Yeah I have a thing about global variables (which static is a kind of) when a normal stack-based variable will do.
    – Blindy
    Commented Sep 26, 2012 at 15:46
  • The use of static provided the initial inspiration. And then, of course, multi-threading should be considered which means that something must be propagated into the parameter when doing the recursive call. This is the first time, that I found the need to count the recursion depth.
    – daparic
    Commented Jul 23, 2020 at 12:59
4

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.

2
  • I was thinking of something like this, but you beat me to it. You should note that the guard-class still has the problem of not being thread-safe. Commented Oct 29, 2010 at 22:41
  • @Mark Ransom, true. A fool-proof improvement would be to replace the static-storage variable with a thread-local-storage variable, either using boost::thread_specific_ptr or the C++0x thread local facilities. Commented Oct 29, 2010 at 22:45
1

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();
}
0

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.

0

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);
}
2
  • 1
    A global is just a static with looser scope. Commented Oct 29, 2010 at 22:42
  • 1
    I'd say a static is just a global really <.<
    – Blindy
    Commented Oct 29, 2010 at 22:49
0

I came here when I sensed that some recursion is required, because I was implementing a function that can validate the chain of trust in a certificate chain. This is not X.509 but instead it is just the basics wherein the issuer key of a certificate must match the public key of the signer.

bool verify_chain(std::vector<Cert>& chain,
              Cert* certificate,
              unsigned char* pOrigin = nullptr, int depth = 0)
{
    bool flag = false;

    if (certificate == nullptr) {
        // use first element in case parameter is null
        certificate = &chain[0];        
    }

    if (pOrigin == nullptr) {
        pOrigin = certificate->pubkey;            
    } else {
        if (std::memcmp(pOrigin, certificate->pubkey, 32) == 0) {
            return false; // detected circular chain
        }
    }

    if (certificate->hasValidSignature()) {
        if (!certificate->isRootCA()) {
            Cert* issuerCert = certificate->getIssuer(chain);
            if (issuerCert) {
                flag = verify_chain(chain, issuerCert, pOrigin, depth+1);
            }
        } else {
            flag = true; 
        }
    }

    if (pOrigin && depth == 1) {
        pOrigin = nullptr;
    }

    return flag;
}

I needed to know the recursion depth so that I can correctly clean up pOrigin. at the right stack frame during the unwinding of the call stack.

I used pOrigin to detect a circular chain, without which the recursive call can go on forever. For example,

  • cert0 signs cert1
  • cert1 signs cert2
  • cert2 signs cert0

I later realized that a simple for-loop can do it for simple cases when there is only one common chain.

bool verify_chain2(std::vector<Cert> &chain, Cert& cert)
{
    Cert *pCert = &cert;
    unsigned char *startkey = cert.pubkey;

    while (pCert != nullptr) {
        if (pCert->hasValidSignature()) {
            if (!pCert->isRootCA()) {
                pCert = pCert->getIssuer(chain);
                if (pCert == nullptr
                || std::memcmp(pCert->pubkey, startkey, 32) == 0) {
                    return false;
                }
                continue;
            } else {
                return true;
            }
        } else {
            return false;
        }
    }

    return false;
}

But recursion is a must when there is not one common chain but instead the chain is within each certificate. I welcome any comments. Thank you.

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.