Writing a recursive lambda

Lambdas are basically unnamed function objects, which means that it should be possible to call them recursively. Indeed, they can be called recursively; however, the mechanism for doing so is not obvious as it requires assigning the lambda to a function wrapper and capturing the wrapper by reference. Though it can be argued that a recursive lambda does not really make sense and that a function is probably a better design choice, in this recipe, we will look at how to write a recursive lambda.

Getting ready

To demonstrate how to write a recursive lambda, we will consider the well-known example of the Fibonacci function. This is usually implemented recursively in C++, as follows:

constexpr int fib(int const n)
{
  return n <= 2 ? 1 : fib(n - 1) + fib(n - 2);
}

Having this implementation as a starting point, let's see how we can rewrite it using a recursive lambda.

How to do it...

In order to write a recursive lambda function, you must do the following:

• Define the lambda in a function scope
• Assign the lambda to an std::function wrapper
• Capture the std::function object by reference in the lambda in order to call it recursively

The following are examples of recursive lambdas:

• A recursive Fibonacci lambda expression in the scope of a function that is invoked from the scope where it is defined:

  void sample()
  {
    std::function<int(int const)> lfib =
      [&lfib](int const n)
      {
        return n <= 2 ? 1 : lfib(n - 1) + lfib(n - 2);
      };
    auto f10 = lfib(10);
  }
  

• A recursive Fibonacci lambda expression returned by a function, which can be invoked from any scope:

  std::function<int(int const)> fib_create()
  {
    std::function<int(int const)> f = [](int const n)
    {
      std::function<int(int const)> lfib = [&lfib](int n)
      {
        return n <= 2 ? 1 : lfib(n - 1) + lfib(n - 2);
      };
      return lfib(n);
    };
    return f;
  }
  void sample()
  {
    auto lfib = fib_create();
    auto f10 = lfib(10);
  }
  

How it works...

The first thing you need to consider when writing a recursive lambda is that a lambda expression is a function object and that, in order to call it recursively from the lambda's body, the lambda must capture its closure (that is, the instantiation of the lambda). In other words, the lambda must capture itself, and this has several implications:

• First of all, the lambda must have a name; an unnamed lambda cannot be captured so that it can be called again.
• Secondly, the lambda can only be defined in a function scope. The reason for this is that a lambda can only capture variables from a function scope; it cannot capture any variable that has a static storage duration. Objects defined in a namespace scope or with the static or external specifiers have static storage duration. If the lambda was defined in a namespace scope, its closure would have static storage duration and therefore the lambda would not capture it.
• The third implication is that the type of the lambda closure cannot remain unspecified; that is, it cannot be declared with the auto specifier. It is not possible for a variable declared with the auto type specifier to appear in its own initializer. This is because the type of the variable is not known when the initializer is being processed. Therefore, you must specify the type of the lambda closure. The way we can do this is by using the general-purpose function wrapper std::function.
• Last, but not least, the lambda closure must be captured by reference. If we capture by copy (or value), then a copy of the function wrapper is made, but the wrapper is uninitialized when the capturing is done. We end up with an object that we are not able to call. Even though the compiler will not complain about capturing by value, when the closure is invoked, an std::bad_function_call is thrown.

In the first example from the How to do it... section, the recursive lambda is defined inside another function called sample(). The signature and the body of the lambda expression are the same as those of the regular recursive function fib (), which was defined in the introductory section. The lambda closure is assigned to a function wrapper called lfib that is then captured by reference by the lambda and called recursively from its body. Since the closure is captured by reference, it will be initialized at the time it has to be called from the lambda's body.

In the second example, we defined a function that returns the closure of a lambda expression that, in turn, defines and invokes a recursive lambda with the argument it was, in turn, invoked with. This is a pattern that must be implemented when a recursive lambda needs to be returned from a function. This is necessary because the lambda closure must still be available at the time the recursive lambda is called. If it is destroyed before that, we are left with a dangling reference, and calling it will cause the program to terminate abnormally. This erroneous situation is exemplified in the following example:

// this implementation of fib_create is faulty
std::function<int(int const)> fib_create()
{
  std::function<int(int const)> lfib = [&lfib](int const n)
  {
    return n <= 2 ? 1 : lfib(n - 1) + lfib(n - 2);
  };
  return lfib;
}
void sample()
{
  auto lfib = fib_create();
  auto f10 = lfib(10);       // crash
}

The solution for this is to create two nested lambda expressions, as shown in the How to do it... section. The fib_create() method returns a function wrapper that, when invoked, creates the recursive lambda that captures itself. This is slightly and subtly, yet fundamentally, different from the implementation shown in the preceding sample. The outer f lambda does not capture anything, especially by reference; therefore, we don't have this issue with dangling references. However, when invoked, it creates a closure of the nested lambda, which is the actual lambda we are interested in calling, and returns the result of applying that recursive lfib lambda to its parameter.

See also

• Using generic and template lambdas to learn how to use auto for lambda parameters and how to define template lambdas in C++20