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.