C++ Recursion Stack Frame Identifier

user_12162096 0
Viewed 47

Take an example:

int foo(){
    if(<THIS IS THE SECOND TIME YOU CALL FOO>) // I need some indicator like this
        return 1;
    else
        return foo();
}

Essentially, I'm looking for an indicator that tells me "hey this is the second time that you have called foo". (I'm trying to avoid using static variables or changing foo function itself, just for sake of this exercise.)

I'm guessing if there's any variable related to the function's current stack frame (or maybe the caller stack frame) which I can exploit and use?

recursion c++
2 Answers

You can leverage a thread_local counter, along with a RAII object to increment a counter at some point in your function and decrement it when the thread leaves the function.

By creating an instance of this object with automatic storage duration (as a local variable) near the top of the function you can know how many times the current thread has called the function without returning yet.

By including an auto template argument, you can also provide the function as the template argument to allow the class to be reused in different functions.

Live example :

template<auto>
class stack_count
{
public:
    stack_count() { 
        counter()++;
    }
    ~stack_count() {
         counter()--;
    }
    
    stack_count(const stack_count&) = delete;
    void operator=(const stack_count&) = delete;

    int get() const {
        return counter();
    }

private:
    static int & counter() {
        thread_local int counter = 0;
        return counter;
    }
};

#include <iostream>

int foo()
{
    stack_count<&foo> counter;

    std::cout << counter.get() << '\n';

    if(counter.get() == 2) {
        return 42;
    }
    else {
        return foo();
    }
}

int main()
{
    const auto result = foo();
    std::cout << "foo() : " << result << '\n';
}
user_73590940

I'm assuming you want to detect when foo has been called recursively, not when it's been called twice.

And I am guessing you're trying to avoid changing the function signature of foo, but can do whatever you want with the implementation. If that's the case, an inner "implementation" (impl) function that lets you pass the recursion count. The original function foo just calls the implementation function with a seed value:

int fooImpl(int count) {
   if (count == 2) {
       // this is the second time you've called foo

       return 0; // return any value you want
   } else {
      return fooImpl(count+1);
   }
}

int foo(){
    return fooImpl(1);
}

And if you don't want to escape the bounds of the function, then use an internal lambda:

int foo() {

std::function<int(int)> fn;

fn = [&fn](int count)->int {
    if (count == 2) {
        // this is the second time you've called foo
        return 0; // return any value you want
    }
    else {
        return fn(count + 1);
    }
};

return fn(1);

}

user_1044580
Related