Recursive lambda functions in C++14

Question

There is an oft-repeated 'trick' to write recursive lambda functions in C++11 that goes as follows:

std::function<int(int)> factorial;
factorial = [&factorial](int n)
{ return n < 2 ? 1 : n * factorial(n - 1); };

assert( factorial(5) == 120 );

(e.g. Recursive lambda functions in C++0x.)

This technique has two immediate drawbacks though: the target of the std::function<Sig> object is tied (via the capture by reference) to a very particular std::function<Sig> object (here, factorial). This means that the resulting functor typically cannot be returned from a function, or else the reference would be left dangling.

Another (although less immediate) problem is that the use of std::function is typically going to prevent compiler optimizations, a side-effect of the need for type-erasure in its implementation. This is not hypothetical and can easily be tested.

In the hypothetical situation where recursive lambda expressions would really be convenient, is there a way to address those issues?

Uhm... obviously not using a lambda expression is the natural option here... — David Rodríguez - dribeas, Aug 06 '13 at 16:20
@LucDanton: If you've chosen to write a recursive lambda in C++, you have chosen *poorly*. There's no reason to do that when you could just write a class inside your function. Yes, it'll be more tedious, but it'll still be easier than the gymnastics you'll need for recursive lambdas. — Nicol Bolas, Aug 06 '13 at 16:37
@LucDanton: Are they really? *Most* of it is in the support component, but the lambda needs to be written to work in that framework and you have to use it within a call to `fix`. Not saying that it is horrible or anything, but this looks as if lambda was the new *golden hammer* and this was adding a screwdriver tip to the handle... — David Rodríguez - dribeas, Aug 06 '13 at 16:55
@dyp that something would be [this](http://coliru.stacked-crooked.com/a/6dea903aa9363232) — RamblingMad, May 28 '14 at 14:07

Luc Danton · Accepted Answer · 2014-08-19T06:11:14.057

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

Not too hard to unroll... one member function `odd`, another `even`, then `operator()` that does the initial dispatch (I must admit I am just blindly guessing, I don't know what you refer to as *even/odd functions*) — David Rodríguez - dribeas, Aug 06 '13 at 16:57
While it explains why you can't easily create recursive lambdas _in general_, I fail to see why it's not allowed for simple captureless lambdas. After all, they can be thought as a simple function, just with local scope. — Dan M., May 27 '19 at 16:22

score 17 · Answer 2 · answered Mar 26 '15 at 12:48

17

It's not a lambda expression, but hardly more code, works with C++98, and can recurse:

struct {
    int operator()(int n) const {
        return n < 2 ? 1 : n * (*this)(n-1);
    }
} fact;
return fact(5);

According to [class.local]/1, it has access to all names that the enclosing function has access to, which is important for private names in a member function.

Of course, not being a lambda, you have to write a constructor if you want to capture state outside the function object.

answered Mar 26 '15 at 12:48

Marc Mutz - mmutz

24,485
12
80
90

3

Honestly, this is the most practical answer to recursive lambda functions. :) – vedranm May 27 '17 at 21:52
best answer in the world – myworldbox Dec 04 '21 at 20:09

Recursive lambda functions in C++14

2 Answers2

What are the costs?

GCC 4.9 examples

Linked