The first thing you need to consider when writing a recursive lambda is that a lambda expression is a function object and, 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 in order to 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, 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 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 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() 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 have 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 sample:

    // 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 the issue with dangling references. However, when invoked, it creates a closure of the nested lambda, the actual lambda we are interested in calling and returns the result of applying that recursive lfib lambda to its parameter.