Recursive lambda functions in C++11
Think about the difference between the auto version and the fully specified type version. The auto keyword infers its type from whatever it's initialized with, but what you're initializing it with needs to know what its type is (in this case, the lambda closure needs to know the types it's capturing). Something of a chicken-and-egg problem.
On the other hand, a fully specified function object's type doesn't need to "know" anything about what is being assigned to it, and so the lambda's closure can likewise be fully informed about the types its capturing.
Consider this slight modification of your code and it may make more sense:
std::function<int(int,int)> sum;
sum = [term,next,&sum](int a, int b)->int {
if(a>b)
return 0;
else
return term(a) + sum(next(a),b);
};
Obviously, this wouldn't work with auto. Recursive lambda functions work perfectly well (at least they do in MSVC, where I have experience with them), it's just that they aren't really compatible with type inference.
Call C++ recursive lambda in the same line where it is declared
Let me offer a glimpse into the functional programming world, where people usually use combinators to deal with recursive lambdas. There was a proposal (P0200r0) last year to add a simple Y-combinator to the standard library.
Leaving aside the question whether it is a good idea to do this, this would allow you to write and invoke a recursive lambda like this:
y_combinator([](auto self, int i){
if (i>1) {
std::cout << "func(a, ";
self(i-1);
std::cout << ")";
} else {
std::cout << "a";
}
})(6);
The basic idea here is that the y-combinator is a higher order function that wraps a lambda which is passed 'itself' as a first argument. The combinator takes care of wrapping the self argument away for all invocations of the lambda.
You can try it in coliru.
Can lambda functions be recursive?
Yes, they can. Starting with C++23 you can use the explicit this parameter:
auto factorial = [](this auto self, int i)
{
return (i == 1) ? 1 : i * self(i - 1);
};
With previous C++ standards, you can store the lambda in a variable and reference that variable (although you cannot declare the type of that variable as auto
, you would have to use an std::function
object instead). For instance:
std::function<int (int)> factorial = [&] (int i)
{
return (i == 1) ? 1 : i * factorial(i - 1);
};
Recursive lambda functions in C++14
The crux of the issue is that in a C++ lambda expression the implicit this
parameter will always refer to the object of the enclosing context of the expression, if present at all, and not the functor object resulting from the lambda expression.
Borrowing a leaf from anonymous recursion (sometimes also known as 'open recursion'), we can use the generic lambda expressions of C++14 to re-introduce an explicit parameter to refer to our would-be recursive functor:
auto f = [](auto&& self, int n) -> int
{ return n < 2 ? 1 : n * self(/* hold on */); };
The caller now has a new burden of making calls of the form e.g. f(f, 5)
. Since our lambda expression is self-referential, it is in fact a caller of itself and thus we should have return n < 2 ? 1 : n * self(self, n - 1);
.
Since that pattern of explicitly passing the functor object itself in the first position is predictable, we can refactor this ugly wart away:
template<typename Functor>
struct fix_type {
Functor functor;
template<typename... Args>
decltype(auto) operator()(Args&&... args) const&
{ return functor(functor, std::forward<Args>(args)...); }
/* other cv- and ref-qualified overloads of operator() omitted for brevity */
};
template<typename Functor>
fix_type<typename std::decay<Functor>::type> fix(Functor&& functor)
{ return { std::forward<Functor>(functor) }; }
This allows one to write:
auto factorial = fix([](auto&& self, int n) -> int
{ return n < 2 ? 1 : n * self(self, n - 1); });
assert( factorial(5) == 120 );
Did we succeed? Since the fix_type<F>
object contains its own functor which it passes to it for each call, there is never a risk of a dangling reference. So our factorial
object can truly be endless copied, moved from, in and out of functions without hassle.
Except... while the 'external' callers can readily make calls of the form factorial(5)
, as it turns out inside our lambda expression the recursive call still looks like self(self, /* actual interesting args */)
. We can improve on this by changing fix_type
to not pass functor
to itself, but by passing *this
instead. That is, we pass in the fix_type
object which is in charge of passing the correct 'implicit-as-explicit' argument in the first position: return functor(*this, std::forward<Args>(args)...);
. Then the recursion becomes n * self(n - 1)
, as it should be.
Finally, this is the generated code for a main
that uses return factorial(5);
instead of the assertion (for either flavour of fix_type
):
00000000004005e0 <main>:
4005e0: b8 78 00 00 00 mov eax,0x78
4005e5: c3 ret
4005e6: 66 90 xchg ax,ax
The compiler was able to optimize everything away, as it would have done with a run-off-the-mill recursive function.
What are the costs?
The astute reader may have noticed one curious detail. In the move from a non-generic to a generic lambda, I added an explicit return type (i.e. -> int
). How come?
This has to do with the fact that the return type to be deduced is the type of the conditional expression, which type depends on the call to self
, which type is being deduced. A quick reading of Return type deduction for normal functions would suggest that rewriting the lambda expression as follows should work:
[](auto&& self, int n)
{
if(n < 2) return 1; // return type is deduced here
else return n * self(/* args */); // this has no impact
}
GCC will in fact accept this code with the first form of fix_type
only (the one that passes functor
). I'm not able to determine if it is right to complain about the other form (where *this
is passed). I leave it to the reader to choose what trade-off to make: less type deduction, or less ugly recursive calls (it's also of course completely possible to have access to either flavour anyway).
GCC 4.9 examples
- Complete code, first flavour
- Complete code, second flavour
- Complete code, first flavour, C++11
- An example of a variadic
fix
for a group of mutually recursive lambda expressions
A Problem with Recursive Void Lambda Expressions in C++
See this question for recursive lamda-functions explanation. You can declare your Lambda as std::function<void(std::vector<int>&)>
and capture it inside lambda:
std::function<void(std::vector<int>&)> Lambda;
Lambda = [&Lambda](std::vector<int>& A) {
while (A.size() < 5) {
A.push_back(1);
Lambda(A);
}
};
Lambda(A);
Recursive call in lambda (C++11)
The reason is that there is no special case for lambda-expression initializers of auto
variables.
Such special cases would be prone to errors and misuses. You need to define the rules when you propose that something like a()
should work. How is the operator()
looked up? What is the precise state of a
's type? Will the type be complete? (which implies that you already know the capture list of the lambda). Once you have formulated that in a format reasonable for a spec, it would be easier to make statements on it.
Allowing your use case would mean yet another case where you need to scan ahead in code, because to determine the type of a
in a()
you must be sure that the initializer ends with nothing that could "unlambda" the type
struct y { void operator()() { } };
template<typename T> y operator+(T, y) { return y(); }
auto x = [] { x(); } + y();
In this case, x()
would call y::operator()
, not the lambda.
As it is now, a
is simply forbidden to be mentioned in its entire initializer. Because in C++, auto
is not a type. It is merely a type specifier standing for a to-be-deduced type. As a consequence, an expression can never have type auto.
Why recursive lambda functions are throwing error when used with auto?
The problem is not the return-type of the lambda expression. The problem is the type of the lambda itself.
Each lambda expression is a unique anonymous type.
In your code, the compiler knows that the lambda returns void, but it doesn't yet know the type of the lambda, since it has not fully parsed it yet.
To give a counter example to highlight the issue.
#include <iostream>
int main()
{
int x;
auto func = [&](){
// func is going to become an int here, but the compiler does not know that yet
// it has to parse the whole expression first.
x = func;
return 5;
}(); // <-- calling the lambda and assigning the return value to func
}
Return recursive lambda from function in C++
If fibonacci (line 2) is a local of the
makeFibonacci()
function, and therefore goes out of scope when the function exits, how can it be captured by reference and used recursively?
It's just chance that the function is working as expected. What you have is undefined behavior. You are referencing an object that goes out of scope in the function.
Also, why does the program segfault when I capture the lambda by copy?
This happens because of how the std::function
is initialized. The lambda is initialized first, the std::function
is initialized with the lambda afterwards. Which means that you are copying an instance of std::function
that is not initialized, and therefore it is probably not in a state which can allow good copies. Invariants are broken inside, which are likely causing the segmentation fault.
You can make a recursive lambda function more efficiently without std::function
by using a polymorphic lambda as follows
auto makeFibonacci() {
auto fib = [](int n, auto& self) {
if (n == 1) {
return 1;
}
if (n == 2) {
return 1;
}
return self(n - 1, self) + self(n - 2, self);
};
return [fib](int n) {
return fib(n, fib);
};
};
Here the lambda owns all the state it needs. You can then use it like this
auto fibonacci = makeFibonacci();
cout << fibonacci(6) << endl;
Also note that this is probably the worst way to calculate fibonacci numbers.
Why is this recursive lambda function unsafe?
This is because in order to be recursive, it uses type erasure and captures the type erased container by reference.
This has the effect of allowing to use the lambda inside itself, by refering to it indirectly using the std::function
.
However, for it to work, it must capture the std::function
by reference, and that object has automatic storage duration.
Your lambda contains a reference to a local std::function
. Even if you return the std::function
by copy, the lambda will still refer to the old one, that died.
To make a secure to return recursive lambda, you can send the lambda to itself in an auto
parameter and wrap that in another lambda:
auto factorial = [](auto self, int i) -> int {
return (i == 1) ? 1 : i * self(self, i - 1);
};
return [factorial](int i) { return factorial(factorial, i); };
Related Topics
Difference in Make_Shared and Normal Shared_Ptr in C++
Namespace + Functions Versus Static Methods on a Class
Static Constant String (Class Member)
Do You Use Null or 0 (Zero) For Pointers in C++
How to Write Iso C++ Standard Conformant Custom New and Delete Operators
C++ "Virtual" Keyword For Functions in Derived Classes. Is It Necessary
What Happens If You Call Erase() on a Map Element While Iterating from Begin to End
Evaluating Arithmetic Expressions from String in C++
What Is the Performance Overhead of Std::Function
Why Should One Not Derive from C++ Std String Class
When Does a Constexpr Function Get Evaluated At Compile Time
Return a 2D Array from a Function
Initializer Lists and Rhs of Operators
Strptime() Equivalent on Windows
Get Human Readable Ast from C++ Code