# 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.