... Probably you haven't seen it before!

Note: There is a shorter and more elegant way of writing recursive functions inside other functions other than using,
auto &&dfs or y_combinator or function<void(...)>

Also note that this is a feature of C++23 and above! So use compiler accordingly.

Hi everyone,
Many of us (maybe not MANY, but still) like to use lambdas as much as possible so that we don’t have to pass disasters like vector<vector<vector<int>>> to globally declared functions. You might think of declaring it globally only, but then you have to resize it according to size and clear/reset it for next testcases, if any. That takes too much writing and thus time, right?

Instead, we can write functions inside functions called lambda functions. This allows us to capture local variables without making them global, making our code shorter and easier to understand. This functions are normal functions (non-recusive)

But what about recursive functions ?

We can use auto for recursive lambdas as well. Let’s go through the evolution of “elegance”:

Elegant method * 1

Use auto dfs(auto &&dfs, ...)
Here, you need to pass the dfs name (function name) everywhere, whenever you call it recursively. Works, but verbose.

void solve() {
    // rest of the stuff

    auto dfs = [&](auto &&dfs, int v){
        vis[v] = 1;
        for(int c : adj[v]) {
            if(vis[c]) continue;
            dfs(dfs, c); // need to pass dfs inside dfs as a function reference 
        }
    };
    dfs(dfs, 0);
}

Elegant method * 10

Use y_combinator snippet
Using this at the very top of your template removes the need for passing function names passing part making it clean. But you have to include this y_combinator code snippet into your code template, which doesn't looks clean. (maybe i have ocd lol)

// y_combinator snippet
template<class Fun> class y_combinator_result {
    Fun fun_;
public:
    template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
    template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); }
};
template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }


void solve(){
    // rest of the stuff 

    auto dfs = [&](int v){
        vis[v] = 1;
        for(int c : adj[v]) {
            if(vis[c]) continue;
            dfs(c);
        }
    };
    dfs(0);
}

Elegant method ^ 10

Use std::function or function<return_type(parameters)>
This avoids passing dfs around without using y_combinator, but declaring function<void(int)> every time looks bulky. You can shorten with macros, but still not the most elegant one!

void solve(){
    // rest of the stuff

    function<void(int)> dfs = [&](int v){
        vis[v] = 1;
        for(int c : adj[v]) {
            if(vis[c]) continue;
            dfs(c);
        }
    };
    dfs(0);
}

Elegant method ^ (10!)

Use this auto <function_name>
Look at the code below

void solve() {
    // rest of the stuff

    auto dfs = [&](this auto dfs, int v){
        vis[v] = 1;
        for(int c : adj[v]) {
            if(vis[c]) continue;
            dfs(c);
        }
    };
    dfs(0);
}

Using auto func = [&](this auto func, ...) {...};, needs no passing of function name like we did before. Just write this 3 magical words "this auto function_name" once and thats it. I haven't seen any more elegant way of writing this yet!

I hope it will help you write cleaner and faster code !

Share you thoughts :
- Didn't know this, thanks a lot
- Knew this for a decade, but thanks anyway
- Want to see me in cry's basement
- I came, I saw, I liked
- Reading this gave me +10 IQ points