# c++ - std::function lambda

## Recursive lambda functions in C++14 (2)

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.

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?

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