kau - 6 months ago 25
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;
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 has me confused is
`return x -> f.apply(Y(f)).apply(x);`
. Isn't
`Y(f)`
a recursive call to the method
`Y`
? We keep calling it with the Function
`f`
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>() {
@Override
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)
.mapToObj(Integer::valueOf)
.map(fib)
.forEach(System.out::println);
``````

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)
.mapToObj(Integer::valueOf)
.map(right())
.forEach(System.out::println);
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download