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); } 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.
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....
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.
static is a kind of) when a normal stack-based variable will do.
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.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.
boost::thread_specific_ptr or the C++0x thread local facilities.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(); } 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.
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); } 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,
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.