How can I write a beautiful inline recursive lambda in C++? [closed]

Question

As I know in C++17, I can write a recursive lambda like this:

auto dfs = [&](const auto &self, int x) -> void {
    // ....
    self(self, x);
};

dfs(dfs, 0);

Unfortunately, I have to endure one more parameter which is a bit ugly. And I doubt the possibility for the compiler to make it inline. Are there new options in new C++ standards? (C++20 or C++23)

Memorialist

You can still create a (old) dedicated type to get rid of self parameter. – Moat

"And I doubt the possibility for the compiler to make it inline." You can always try it and see – Salesmanship

If a dedicated type like std::function is used, there will be performance lost. – Memorialist

@JunhuiZhu A dedicated type like struct { int& capture1; void operator()(int x) const { ...; (*this)(x); } } dfs{ captured1 };, where you have access to *this of the functor – Overpass

That's also an option. Get it. – Memorialist

Off-topic/personal opinion: For me lambda is a tool which is and adapter for calling some API (like algorithms). If you need name a lambda to do something strange why not just use some old fashioned function or a class. This way code is easier to test you have reusable logic and recursion is not a problem. Lambdas are powerful tool, but IMO they tend to be overused. – Klara

Note, your request to "make it inline" will mean your compiled program will be infinite in size. Make sure your computer is equipped with an infinite amount of RAM, and has sufficient hard drive space for infinite bytes. (Same issue with struct Foo { int x{}; Foo foo; }; being infinite in size.) – Normalie

@Normalie Unless of course the optimizer transforms recursion into iteration – Sexdecillion

Answer 1

You can use an explicit object parameter with a deduced type:

auto dfs = [&](this const auto &self, int x) -> void {
    // ....
    self(x);
};

dfs(0);  // `self` is `dfs`

This is a C++23 feature

Overpass

Will this be inlined? – Memorialist

@JunhuiZhu self should be passed exactly the same as the this pointer was to an implicit object function (since a reference should use the same abi as a pointer), so no extra work is done unlike passing an extra dfs(dfs, 0) – Overpass

@JunhuiZhu I see you are fixed on "it must be inlined". Why do you care? Prefomance? Do you measure it? Let compiler decide what is worth inline and what not. In fact recursion increases chance of preventing inlineing code. If tail recursion cold not be used by copiler, then actual function is required and compiler can't inline code. – Klara

It is of course not possible to inline a function into itself unless you do constant propagation and the inlined function is simplified. In the example you give, inline a function into itself will double the size of the function, inlining it again will make it even bigger, etc. The only place where you can optimize a function calling itself is by using tail-recursion, which is not inlining but replacing a function call by a jump instruction. – Claudie

Answer 2

If you don't have access to C++23 then you can wrap your lambda in another lambda that hides the extra argument, e.g. like this:

int main(int argc, char **argv) {
    auto fact = [&](int x) -> int {
        auto do_fact = [&](const auto &self, int x) -> int {
            return x ? x * self(self, x - 1) : 1;
        };
        return do_fact(do_fact, x);
    };
    return fact(argc);
}

clang with -O and gcc with -O2 will compile the above into a simple multiplication loop (clang tries to be extra clever at higher optimisation levels).

Retread

Answer 3

I'm not sure if this counts as beautiful, but you might consider this:

std::function<void(int)> dfs = [&](int x) -> void {
    // ....
    dfs(x);
};

dfs(0);

The compiler may be able to inline the std::function call, but only in simple cases. Of course, it cannot fully inline a recursive function.

Gerber