Recursive Lambda Function in C++

1. C++ Recursive Lambda Function
2. C++ Recursive Lambda Function Using std::function
3. C++ Recursive Lambda Function Using Generic Lambda
4. C++ Recursive Lambda Function Using y_combinator

In this article, we will understand the recursive lambdas available in C++.

C++ Recursive Lambda Function

Recursion refers to a process by which a function (directly or indirectly) calls itself, and the function corresponding to this process is called a Recursive Function. A recursive lambda expression is the result of this process.

When some issues are approached using a recursive method, they are much simpler to resolve.

In the process of restructuring local code, lambdas are a helpful tool. On the other hand, there are instances when we wish to utilize the lambda from inside itself.

This may be done for one of two reasons: to enable direct recursion or to make it possible for the closure to be registered as a continuation. The present version of C++ makes this task extremely tough to do successfully.

Implementation of the Recursive Lambda Function in C++

In the first step, we will import the necessary libraries.

#include <functional>
#include <iostream>

Inside the main() function, initialize a variable of int type and assign it an integer value.

int main() { int anyNumber = 456789; }

Then, create a function with the type void and give it the name reverseByRecursiveLambda.

function<void()> reverseByRecursiveLambda;

Now, initialize the reverseByRecursiveLambda function with a recursive lambda function.

reverseByRecursiveLambda = [&]() {};

Inside this method, you should implement a check that says if the integer value of anyNumber is equal to 0, you should return nothing. If this is not the case, the function should go on to the next set of operations.

Then, the function will carry out a series of mathematical computations, after which it will print the results. As the last step, it will run the function named reverseByRecursiveLambda() again.

if (anyNumber == 0) return;

cout << anyNumber % 10 << " ";
anyNumber /= 10;
reverseByRecursiveLambda();

After this function has completed execution, the only thing required is a call to this function inside the main() method.

int main() { reverseByRecursiveLambda(); }

Complete Source Code:

#include <functional>
#include <iostream>

using namespace std;

int main() {
  int anyNumber = 123456789;

  function<void()> reverseByRecursiveLambda;

  reverseByRecursiveLambda = [&]() {
    if (anyNumber == 0) return;

    cout << anyNumber % 10 << " ";
    anyNumber /= 10;
    reverseByRecursiveLambda();
  };

  reverseByRecursiveLambda();
}

Output:

9 8 7 6 5 4 3 2 1

C++ Recursive Lambda Function Using std::function

The std::function class template is a polymorphic function wrapper that may be used for various purposes. Any lambda expressions bind expressions, or other function objects may be stored, copied, and invoked inside instances of the std::function class.

In addition, these instances can hold pointers to member functions and pointers to data members.

In the following example, we need to take a snapshot of the factorial, after which we can reference it inside the lambda body.

Example Code:

#include <functional>
#include <iostream>

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

  std::cout << "The factorial of 5 is: " << factorial(5);
  return factorial(5);
}

Output:

The factorial of 5 is: 120

C++ Recursive Lambda Function Using Generic Lambda

Generic Lambda Expression refers to a lambda expression with at least one argument of the auto type.

The use of std::function is not required to create recursive lambda functions, thanks to the generic lambda expression, which made this option possible. The type of a lambda expression cannot be determined by its name alone.

Therefore, before the release of C++14, a recursive lambda expression was required to be enclosed inside a std::function. It is not dependent on std::function, and it does not need to capture any data to perform properly on any numeric base type.

In the example, we will demonstrate how to show the data stored in a map using the generic lambda auto.

Example Code:

#include <algorithm>
#include <iostream>
#include <map>
#include <string>

int main() {
  const std::map<std::string, int> numbers{
      {"Saad", 22}, {"Zaryab", 23}, {"Zeeshan", 24}};

  std::for_each(std::begin(numbers), std::end(numbers), [](const auto& entry) {
    std::cout << "Name: " << entry.first << "   Age: " << entry.second << '\n';
  });
}

GCC 11.1.0 is the name of the compiler that is being used in this demonstration.

Output:

Name: Saad   Age: 22
Name: Zaryab   Age: 23
Name: Zeeshan   Age: 24

C++ Recursive Lambda Function Using y_combinator

Since anonymous functions (also known as lambdas) are only meant to be used when the logic is straightforward and should be extracted to a named function, it is improbable that a recursive call would be made inside a lambda.

Let’s imagine, however, that we can’t utilize recursion. As long as functions are treated as first-class citizens in our language (they may be assigned to variables, supplied as arguments, and returned like any other object), we can still write our recursion implementation.

The Y combinator is a useful higher-order function for this purpose. Despite its ominous-sounding name, it is only a higher-order function, a function that wraps around another function.

The following is an example of creating a recursive lambda function using the y combinator to list the Fibonacci series.

Example Code:

#include <iostream>

template <typename Function>
struct YCombinator {
  Function yFunction;

  template <typename... Args>
  decltype(auto) operator()(Args&&... args) {
    return yFunction(*this, std::forward<Args>(args)...);
  }
};

template <typename Function>
decltype(auto) make_YCombinator(Function f) {
  return YCombinator<Function>{f};
}

int main() {
  auto fib = make_YCombinator([](auto self, int n) {
    if (n < 2) return 1;
    return self(n - 1) + self(n - 2);
  });

  for (int i = 0; i < 10; ++i)
    std::cout << "fib(" << i << ") = " << fib(i) << "\n";

  return 0;
}

GCC 11.1.0 is the name of the compiler that is being used in this demonstration.

Output:

fib(0) = 1
fib(1) = 1
fib(2) = 2
fib(3) = 3
fib(4) = 5
fib(5) = 8
fib(6) = 13
fib(7) = 21
fib(8) = 34
fib(9) = 55