# Recursive lambdas

suggest changeLet’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.