 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;
public:
constexpr Y(F f) : f(std::forward<F>(f)) {}
template <typename...Ts>
constexpr decltype(auto) operator()(Ts&&...ts) {
return f(*this,
std::forward<Ts>(ts)...);
}
};
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);
}
}

Example

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.

Further Aspects

---

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