jambit ToiletPaper: Rekursion mit anonymen Funktionsobjekten

Recursion With Anonymous Function Objects

Problem: How to call an anonymous method recursively?

In the recent past, C++ (since C++11), Java (since version 8) and many other languages have been extended by "lambdas". In practice, this is a shortened notation to define an anonymous class with a functional interface and at the same time instantiate an object of this class. But how to call an anonymous method recursively?!?

Solution: The fixed-point combinator

Even though it is possible to create lambdas à la std::function<void()> f = [f]() { /* ... */ f(); }; in C++, it only works with an additional indirection (e.g. via std::function) and not inline (e.g. as parameter). For Java, it does not look any better. A more elegant way is to use the "Y combinator" (you might search the internet for "fixed-point combinator"): You replace the recursive function with a higher-order function that calls its parameter instead of itself. You put this function into the Y combinator, which repeatedly calls the function with itself as parameter.

And what does this mysterious combinator look like? Here are possible implementations in C++ (for any number of parameters of any type) and Java (with currying for the function and an additional parameter):

C++ (for any number of parameters of any type)
template <typename F>
class Y {
  F f;
  constexpr Y(F f) : f(std::forward<F>(f)) {}
  template <typename...Ts>
  constexpr decltype(auto) operator()(Ts&&...ts) {
    return f(*this,
Java (with currying for the function and an additional parameter)
class Y<T, R> implements Function<T, R> {
  private Function<Function<T, R>,
          Function<T, R>> f;
  public Y(Function<Function<T, R>,
           Function<T, R>> f) {
    this.f = f;
  public R apply(T t) {
    return f.apply(this).apply(t);


Let's have a look at the standard example for recursion, the factorial. As a function (in C++), and as a lambda in C++17/Java, it looks like in the image.

The trailing return type is unfortunately needed in C++, because otherwise the compiler triggers "auto type deduction", which leads to a cyclic dependency.

Fakultät als Funktion (in C++), sowie als Lambda in C++17/Java

Further Aspects


Author: Andreas Swoboda / Software Engineer / Business Division Banking & Insurance

Recursion With Anonymous Function Objects

Cookie Settings

This website uses cookies to personalize content and ads, provide social media features, and analyze website traffic. In addition, information about your use of the website is shared with social media, advertising, and analytics partners. These partners may merge the information with other data that you have provided to them or that they have collected from you using the services.

For more information, please refer to our privacy policy. There you can also change your cookie settings later on.

contact icon

Contact us now