Recursive lambdas

Let’s say we wish to write Euclid’s gcd() as a lambda. As a function, it is:

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a%b);
}

But a lambda cannot be recursive, it has no way to invoke itself. A lambda has no name and using this within the body of a lambda refers to a captured this (assuming the lambda is created in the body of a member function, otherwise it is an error). So how do we solve this problem?

Use std::function

We can have a lambda capture a reference to a not-yet constructed std::function:

std::function<int(int, int)> gcd = [&](int a, int b){
    return b == 0 ? a : gcd(b, a%b);
};

This works, but should be used sparingly. It’s slow (we’re using type erasure now instead of a direct function call), it’s fragile (copying gcd or returning gcd will break since the lambda refers to the original object), and it won’t work with generic lambdas.

Using two smart pointers:

auto gcd_self = std::make_shared<std::unique_ptr< std::function<int(int, int)> >>();
*gcd_self = std::make_unique<std::function<int(int, int)>>(
  [gcd_self](int a, int b){
    return b == 0 ? a : (**gcd_self)(b, a%b);
  };
};

This adds a lot of indirection (which is overhead), but it can be copied/returned, and all copies share state. It does let you return the lambda, and is otherwise less fragile than the above solution.

Use a Y-combinator

With the help of a short utility struct, we can solve all of these problems:

template <class F>
struct y_combinator {
    F f; // the lambda will be stored here

    // a forwarding operator():
    template <class... Args>
    decltype(auto) operator()(Args&&... args) const {
        // we pass ourselves to f, then the arguments.
        // the lambda should take the first argument as `auto&& recurse` or similar.
        return f(*this, std::forward<Args>(args)...);
    }
};
// helper function that deduces the type of the lambda:
template <class F>
y_combinator<std::decay_t<F>> make_y_combinator(F&& f) {
    return {std::forward<F>(f)};
}
// (Be aware that in C++17 we can do better than a `make_` function)

we can implement our gcd as:

auto gcd = make_y_combinator(
  [](auto&& gcd, int a, int b){
    return b == 0 ? a : gcd(b, a%b);
  }
);

The y_combinator is a concept from the lambda calculus that lets you have recursion without being able to name yourself until you are defined. This is exactly the problem lambdas have.

You create a lambda that takes “recurse” as its first argument. When you want to recurse, you pass the arguments to recurse.

The y_combinator then returns a function object that calls that function with its arguments, but with a suitable “recurse” object (namely the y_combinator itself) as its first argument. It forwards the rest of the arguments you call the y_combinator with to the lambda as well.

In short:

auto foo = make_y_combinator( [&](auto&& recurse, some arguments) {
  // write body that processes some arguments
  // when you want to recurse, call recurse(some other arguments)
});

and you have recursion in a lambda with no serious restrictions or significant overhead.