kau kau - 26 days ago 9
Java Question

How is this piece of Recursive lambda call in Java working

I recently came across this piece of code in Java. It involves Function and printing fibonacci numbers and it works.

public class AppLambdaSubstitution {

public static Function<Integer, Integer> Y(Function<Function<Integer, Integer>, Function<Integer, Integer>> f) {
return x -> f.apply(Y(f)).apply(x);

public static void main(String[] args) {
Function<Integer, Integer> fib = Y(
func -> x -> {
if (x < 2)
return x;
return func.apply(x - 1) + func.apply(x - 2);


The part that has me confused is
return x -> f.apply(Y(f)).apply(x);
. Isn't
a recursive call to the method
? We keep calling it with the Function
as a parameter. To me, there's no base case for this recursive call to return from. Why is there no overflow resulting from an endless recursive call?

Answer Source

Fundamentally you are missing the point that x -> f.apply(Y(f)).apply(x); will not call apply, it will return a Function.

That's just a very complicated (and non-intuitive?) way of showing currying and recursive function IMO. Things would be much simpler if you would replace a couple of things and make it a bit more readable.

This construction:

 Function<Function<Integer, Integer>, Function<Integer, Integer>>

is not needed at all, since the left parameter is not used at all. It's simply needed to get a hold of the right one. As such the left parameter could be anything at all (I will later replace it with Supplier - that is not needed either, but just to prove a point).

Actually all you care about here is this Function that does the actual computation for each element of the Stream:

 public static Function<Integer, Integer> right() {

    return new Function<Integer, Integer>() {
        public Integer apply(Integer x) {
            if (x < 2) {
                return x;
            } else {
                return apply(x - 1) + apply(x - 2);

Now you could write that entire construct with:

 Supplier<Function<Integer, Integer>> toUse = () -> right();
 Function<Integer, Integer> fib = curry(toUse);
 IntStream.range(1, 11)

This Supplier<Function<Integer, Integer>> toUse = () -> right(); should make you understand why in the previous example (Function<Function, Function>) the left part was needed - just to get a hold of the right one.

If you look even closer, you might notice that the Supplier is entirely not needed, thus you could even further simplify it with:

IntStream.range(1, 11)