There are algorithms that have natural recursive representation and are very cumbersome or painful to write iteratively. With the advent of lambda expressions in C++11, it seemed just natural that they should support recursive calls. But the reality hit hard, recursion and lambdas hadn’t mixed at all until C++14, and even then the support was far from programmer-friendly. The newest C++ edition finally brings the possibility to create a recursive lambda to the table.

Take a look at the classical Fibonacci sequence implementation:

```
long fibonacci(int n) {
return n < 2 ? n : fibonacci(n-1) + fibonacci(n-2);
}
```

That’s it–a single line of code that contains two *recursive calls* is all you need. Compare this with the iterative variant:

```
long fibonacci(int n) {
if (n < 2)
return n;
long a{0}, b{1};
while(--n){
auto temp = a + b;
a = b;
b = temp;
}
return b;
}
```

Long and ugly, and doesn’t look like the *Fibonacci sequence* at all, right? The recursive version, on the other hand is both compact and very readable.

*Lambda expressions*, introduced in C++11, were advertised as a perfect solution for simple, short functions. Precisely the case of the `fibonacci`

in its recursive flavor. If that’s what you thought, you are up for a big disappointment. The *obvious* lambda solution:

```
int main(){
auto fibonacci = [](int n) -> long {
return n < 2 ? n : fibonacci(n-1) + fibonacci(n-2);
};
std::cout << fibonacci(10); // should print 55
}
```

Fails to compile, with an all-telling error that a lambda expression cannot be used before it’s fully defined. That is, you cannot refer to a lambda expression within it, because it’s still not fully known to the compiler. That’s both disappointing and seemingly silly because a *function object* equivalent compiles and works just fine:

```
struct fibonacci {
long operator()(int n) const noexcept {
return n < 2 ? n : operator()(n-1) + operator()(n-2);
}
};
int main(){
std::cout << fibonacci{}(10); // should print 55
}
```

And at their heart, lambdas are nothing more but sugar coating applied on top of *function objects*. Nevertheless, the recursive lambda solution doesn’t work. At this moment you could stop and give up. But let’s be honest, lambdas are made for short single-use functions (like `fibonacci`

) and, on top of that, they have a certain allure to them.

## Making lambdas recursive with C++14

A *recursive function* must be able to refer itself. Here’s the problem, the only way for a lambda expression to know about other objects, including itself, is to either capture them or pass as arguments. Capturing won’t help because you cannot capture something that doesn’t exist yet:

```
auto fibonacci = [&fibonacci](int n) -> long { /* ... */}; // ERROR
```

So this approach is a no-go. To use the second one, *argument passing approach*, the parameter’s type needs to be known. Unfortunelty, lambdas don’t come with type names known to the programmer, and the only solution seems to be `decltype`

:

```
auto fibonacci = [](const decltype(fibonacci)& self, int n) -> long { /*...*/ }; // ERROR
```

But this cannot work! The `fibonacci`

’s type is not yet known when it’s used in the `decltype`

specifier.

At moments as such, when the compiler doesn’t seem to appreciate just how badly you want to bend the type system to your needs, templates usually come to mind. Luckily, partial support for templates was added to lambdas in C++14. In this limited form, a lambda expression can have generic parameters specified with the placeholder `auto`

. And so, `fiboncci`

spiked with generics becomes:

```
auto fibonacci = [](const auto& self, int n) -> long {
return n < 2 ? n : self(self, n-1) + self(self, n-2);
};
```

Let’s zoom in on it. The generic `fibonacci`

takes, as its first argument, `self`

of some unknown, templated, `auto`

type. Later, in the lambda’s body, `self`

is used as a function and passed two arguments, `self`

(again), and the integer `n`

(less one or two). The call to `self`

is what makes `fibonacci`

recursive. To use it, you’ll need to pass the lambda expression to itself, and let the compiler figure out the types:

```
auto fibonacci = /* ... */ ;
std::cout << fibonacci(fibonacci, 10);
```

And… it just works. But, there’s an elephant in the room…

## Making lambda’s recursive with higher-order functions

Using `fibonacci`

became unintuitive at best. There’s an explicit `self`

argument that needs to be passed, making the function useless in most commonplace scenarios. As it often happens, the solution is adding another layer of indirection. By *embedding* the renamed `fibonacci`

within another lambda expression, you can finally enjoy a fully recursive lambda with natural syntax:

```
auto fibonacci_impl = [](const auto& self, int n) -> long{
return n < 2 ? n : self(self, n-1) + self(self, n-2);
};
auto fibonacci = [&fibonacci_impl](int n){
return fibonacci_impl(fibonacci_impl, n);
};
std::cout << fibonacci(10);
```

In fact, this technique is so useful, that you might be tempted to write a specialized, generic function that makes other functions recursive:

```
template <typename F>
auto make_recursive(F&& f){
return [f=std::forward<F>(f)](auto...args){
return f(f, std::forward<decltype(args)>(args)...);
};
}
```

Unsurprisingly, this *higher-order* function has a name, the Y-combinator. It allows for making recursive functions in languages that don’t support them directly. It doesn’t look very appealing, because of the lack of explicit type parameters in C++14 lambdas, so let’s rewrite it in C++20, which supports fully-fledged templates for lambda expressions. Better yet, let’s turn everything into lambdas!

```
auto make_recursive = []<typename F>(F&& f) -> decltype(auto) {
return [f=std::forward<F>(f)]<typename...Args>(Args&&...args) -> decltype(auto) {
return f(f, std::forward<Args>(args)...);
};
};
auto fibonacci = make_recursive(fibonacci_impl);
std::cout << fibonacci(10);
```

I agree, it looks intimidating at first, so let’s dissect it. `make_recursive`

is a lambda that takes a generic *function object*, like `fibonacci_impl`

, and returns another lambda. When you call `make_recursive`

, you’ll get this lambda back. Consequently, `fibonacci`

in the snippet above is nothing else but the lambda returned by `make_recursive`

. This *returned* lambda does all the work. First, it captures the *function object*, `f`

, passed to `make_recursive`

. `f`

is *forwarded* in its capture-list, meaning that it will be either copied or moved into it. To support any scenario, the *returned* lambda accepts a *parameter pack* as its argument. As a result, it can take any number of arguments, ranging from zero to whatever seems reasonable. Those arguments are *forwarded* to the captured `f`

when calling it, making for transparent experience. You could possibly go one step further and implement `make_recursive`

using `std::invoke`

:

```
auto make_rec = []<typename F>(F&& f) -> decltype(auto) {
return [f=std::forward<F>(f)]<typename...Args>(Args&&...args) ->decltype(auto) {
return std::invoke(f, f, std::forward<Args>(args)...);
};
};
```

Which should make `make_rec`

work nicely with other function-like objects besides lambdas.

## Going self-sufficient with C++23

The story doesn’t end here. As it turns out, support for explicit recursive lambdas was on many whish lists. The ideas ranged from just allowing recursive calls to `operator()`

to specialized syntaxes like:

```
auto fibonacci = []internal_name(int n) -> long {
return n < 2 ? n : internal_name(n-1) + internal_name(n-2);
}
```

None of those ideas made it through though, because there was a bigger fish to catch. It materialized in C++23 as a core-language feature, *deducing this*. Simply put, *deducing this* introduces the ability to have an explicit `this`

parameter in member functions. The current object instance, `this`

, has been always invisibly passed to all non-static member functions, but now you can make `this`

visible and extremely usable. Compare the two operators below:

```
struct fibonacci {
// implicit this passed
long operator()(int n) {
return n < 2 ? n : operator()(n-1) + operator()(n-2);
}
// explicit this passed as `self`
long operator()(this const fibonacci& self, int n) {
return n < 2 ? n : self(n-1) + self(n-2);
}
};
```

The second version uses the explicit `this`

parameter syntax introduced in C++23. In the scope of the `operator()`

, the current object is known as `self`

and it can be used to make a recursive call, instead of `operator()`

.

How does it help with lambdas? The really powerful idea in *deducing this* is embedded within the first word, *deducing*. The type of `this`

doesn’t need to be specified, it can be deduced by the compiler. And so, the recursive `operator()`

in the `fibonacci`

structure above, could be written as:

```
long operator()(this const auto& self, int n) {
return n < 2 ? n : self(n-1) + self(n-2);
}
```

Applying this idea to lambdas, you’ll get:

```
auto fibonacci = [](this const auto& self, int n) -> long {
return n < 2 ? n : self(n-1) + self(n-2);
}
```

Clear, concise and works just fine. If you want to try *deducing this*, you’ll have to use the *msvc* compiler–at the time of writing, it is the only one supporting this feature.