Implement recursive lambda function using Java 8

Question

Java 8 introduced lambda functions and I want to implement something like factorial:

 IntToDoubleFunction fact = x -> x == 0 ? 1 : x * fact.applyAsDouble(x-1);

Compilation returns

  error: variable fact might not have been initialized

How can I reference function itself. Class is anonymous but instance exists: It is called fact.

Solution 1

I usually use (once-for-all-functional-interfaces defined) generic helper class which wraps the variable of the functional interface type. This approach solves the problem with the local variable initialization and allows the code to look more clearly.

In case of this question the code will look as follows:

// Recursive.java
// @param <I> - Functional Interface Type
public class Recursive<I> {
    public I func;
}

// Test.java
public double factorial(int n) {

    Recursive<IntToDoubleFunction> recursive = new Recursive<>();
    recursive.func = x -> (x == 0) ? 1 : x * recursive.func.applyAsDouble(x - 1);

    return recursive.func.applyAsDouble(n);
}

Solution 2

One way is to write a secondary function, helper, which takes a function and a number as arguments, and then write the function you actually want, fact = helper(helper,x).

Like so:

BiFunction<BiFunction, Double, Double> factHelper =
        (f, x) -> (x == 0) ? 1.0 : x*(double)f.apply(f,x-1);
Function<Double, Double> fact =
        x -> factHelper.apply(factHelper, x);

This seems to me to be slightly more elegant than relying on corner case semantics like a closure that captures a reference to a mutable structure, or allowing self-reference with a warning of the possibility of "might not be initialized."

Still, it's not a perfect solution because of Java's type system -- the generics cannot guarantee that f, the argument to factHelper, is of the same type as factHelper (i.e. same input types and output types), since that would be an infinitely nested generic.

Thus, instead, a safer solution might be:

Function<Double, Double> fact = x -> {
    BiFunction<BiFunction, Double, Double> factHelper =
        (f, d) -> (d == 0) ? 1.0 : d*(double)f.apply(f,d-1);
    return factHelper.apply(factHelper, x);
};

The code smell incurred from factHelper's less-than-perfect generic type is now contained (or, dare I say, encapsulated) within the lambda, ensuring that factHelper will never be called unknowingly.

Solution 3

Local and anonymous classes, as well as lambdas, capture local variables by value when they are created. Therefore, it is impossible for them to refer to themselves by capturing a local variable, because the value for pointing to themself does not exist yet at the time they are being created.

Code in local and anonymous classes can still refer to themselves using this. However, this in a lambda does not refer to the lambda; it refers to the this from the outside scope.

You could capture a mutable data structure, like an array, instead:

IntToDoubleFunction[] foo = { null };
foo[0] = x -> { return  ( x == 0)?1:x* foo[0].applyAsDouble(x-1);};

though hardly an elegant solution.

Solution 4

If you find yourself needing to do this sort of thing often, another option is to create a helper interface and method:

public static interface Recursable<T, U> {
    U apply(T t, Recursable<T, U> r);
}

public static <T, U> Function<T, U> recurse(Recursable<T, U> f) {
    return t -> f.apply(t, f);
}

And then write:

Function<Integer, Double> fact = recurse(
    (i, f) -> 0 == i ? 1 : i * f.apply(i - 1, f));

(While I did this generically with reference types, you can also make primitive-specific versions).

This borrows from an old trick in The Little Lisper for making unnamed functions.

I'm not sure I'd ever do this in production code, but it is interesting...

Solution 5

Answer is : You have to use a this before name variable calling applyAsDouble function :-

IntToDoubleFunction fact = x -> x == 0 ? 1 : x * this.fact.applyAsDouble(x-1);

if you make the fact final also it will work

final IntToDoubleFunction fact = x -> x == 0 ? 1 : x * this.fact.applyAsDouble(x-1);

We can use functional interface UnaryOperator here. A unary operator that always returns its input argument.

1) Just add this. before the name of the function, as in:

UnaryOperator<Long> fact = x -> x == 0 ? 1  : x * this.fact.apply(x - 1 );

This will hep to avoid “Cannot reference a field before it is defined”.

2) If you prefer a static field, just replace ' this ' with name of the class:

static final UnaryOperator<Long> fact = x -> x== 0? 1: x * MyFactorial.fact.apply(x - 1 );

View more solutions