How does this part of recursive lambda call in Java work

Question

I recently came across this piece of Java code. It includes a function and print 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; else return func.apply(x - 1) + func.apply(x - 2); }); IntStream.range(1,11). mapToObj(Integer::valueOf). map(fib).forEach(System.out::println); } } 

The part that confused me is return x -> f.apply(Y(f)).apply(x); . Is Y(f) recursive call to method Y ? We continue to call it with the function f as a parameter. For me there is no base case for this recursive call to return. Why is there no overflow caused by an infinite recursive call?

Answer 1

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

It's just a very complicated (and unintuitive?) Way to display curry and the recursive IMO function. Everything will be much simpler if you replace a couple of things and make them more readable.

This design:

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

not required at all, since the left parameter is not used at all. It was just necessary to catch the right one. Thus, the left parameter can be something at all (later I will replace it with Supplier - this is also not necessary, but simply in order to prove the point).

In fact, all you need is a Function that does the actual calculation for each Stream element:

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

Now you can write the whole construct with:

  Supplier<Function<Integer, Integer>> toUse = () -> right(); Function<Integer, Integer> fib = curry(toUse); IntStream.range(1, 11) .mapToObj(Integer::valueOf) .map(fib) .forEach(System.out::println); 

This Supplier<Function<Integer, Integer>> toUse = () -> right(); should help you understand why in the previous example ( Function<Function, Function> ) the left part was needed - just to keep right .

If you look even closer, you may notice that Supplier not required , so you can further simplify it with:

 IntStream.range(1, 11) .mapToObj(Integer::valueOf) .map(right()) .forEach(System.out::println);