72

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.

0

26 Answers 26

53

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);
}
1
  • 3
    I've made a utility class so you can pass a recursive closure and get one of the predefined functional types: github.com/claudemartin/Recursive You always have an additional parameter named "self" to do the recursion. Some even have a version with a cache and the Demo.class shows how you can get a rather fast version of the Fibonacci function. May 13, 2015 at 5:13
25

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.

2
  • The Java compiler gives the warning that BiFunction inside BiFunction is not parametrized. You can put this line in the fact lambda as the first line: interface Helper extends BiFunction<Helper, Double> {}; and then use Helper instead of BiFunction. Mar 2 at 11:34
  • Also, there are ToDoubleBiFunction which would be better than BiFunction, and UnaryDoubleOperator instead of Function<Double, Double>. Anyways, great answer, upvoted Mar 2 at 11:35
18

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.

1
  • I like this way (wrapping lambda in 1 element array) as it doesn't require an externally defined helper class or interface. I agree it's not elegant, but it is brief. Jul 26, 2023 at 4:55
13

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...

2
  • 6
    For reference, this approach is generally known in functional programming circles as a "fixed point combinator", and is quite widely used.
    – Jules
    Jun 18, 2018 at 0:51
  • 1
    It might also be nicer to extend Function<T, U> and specify a default apply that kicks off the recursion.
    – austin_ce
    Jan 4, 2021 at 19:28
6

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 );
3

One solution is to define this function as an INSTANCE attribute.

import java.util.function.*;
public class Test{

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

    public static void main(String[] args) {
      Test test = new Test();
      test.doIt();
    }

    public void doIt(){
       System.out.println("fact(3)=" + fact.applyAsDouble(3));
    }
}
1
3
public class LambdaExperiments {

  @FunctionalInterface
  public interface RFunction<T, R> extends Function<T, R> {
    R recursiveCall(Function<? super T, ? extends R> func, T in);

    default R apply(T in) {
      return recursiveCall(this, in);
    }
  }

  @FunctionalInterface
  public interface RConsumer<T> extends Consumer<T> {
    void recursiveCall(Consumer<? super T> func, T in);

    default void accept(T in) {
      recursiveCall(this, in);
    }
  }

  @FunctionalInterface
  public interface RBiConsumer<T, U> extends BiConsumer<T, U> {
    void recursiveCall(BiConsumer<T, U> func, T t, U u);

    default void accept(T t, U u) {
      recursiveCall(this, t, u);
    }
  }

  public static void main(String[] args) {
    RFunction<Integer, Integer> fibo = (f, x) -> x > 1 ? f.apply(x - 1) + f.apply(x - 2) : x;

    RConsumer<Integer> decreasingPrint = (f, x) -> {
      System.out.println(x);
      if (x > 0) f.accept(x - 1);
    };

    System.out.println("Fibonnaci(15):" + fibo.apply(15));

    decreasingPrint.accept(5);
  }
}

During my tests, this is the best that i could achieve for local recursive lambdas. They can be used in streams as well but we loose the easyness of the target typing.

1
  • I think this is the best approach. You can also do RBiFunction @FunctionalInterface interface RBiFunction<T, U, R> extends BiFunction<T, U, R> { @Override default R apply (T t, U u) { return applyRecursive(this, t, u); } R applyRecursive(RBiFunction<T, U, R> self, T t, U u); } Oct 7, 2022 at 13:59
2

Another version using accumulator so that recursion can be optimised. Moved to Generic interface definition.

Function<Integer,Double> facts = x -> { return  ( x == 0)?1:x* facts.apply(x-1);};
BiFunction<Integer,Double,Double> factAcc= (x,acc) -> { return (x == 0)?acc:factAcc.apply(x- 1,acc*x);};
Function<Integer,Double> fact = x -> factAcc.apply(x,1.0) ;

public static void main(String[] args) {
   Test test = new Test();
   test.doIt();
}

 public void doIt(){
int val=70;
System.out.println("fact(" + val + ")=" + fact.apply(val));
}
}
2

You can define a recursive lambda as an instance or class variable:

static DoubleUnaryOperator factorial = x -> x == 0 ? 1
                                          : x * factorial.applyAsDouble(x - 1);

for example:

class Test {
    static DoubleUnaryOperator factorial = x -> x == 0 ? 1
                                             : x * factorial.applyAsDouble(x - 1));
    public static void main(String[] args) {
        System.out.println(factorial.applyAsDouble(5));
    }
}

prints 120.0.

4
  • 1
    Right. The recursion feature on local variables was removed. See this email thread: mail.openjdk.java.net/pipermail/lambda-dev/2013-September/… Feb 8, 2014 at 18:11
  • @StuartMarks But it still works on instance/class variables, right?
    – assylias
    Feb 8, 2014 at 18:14
  • 1
    In simple cases, yes, but you get a warning about factorial potentially not being initialized. I don't believe there is actually a problem in this example, since the lambda cannot be called before it's initialized, but I'm sure someone could come up with a sufficiently complicated example that ended up observing a field in an uninitialized state. At some point it seems preferable to use named methods and method references. See my answer here: stackoverflow.com/a/21652054/1441122 Feb 8, 2014 at 21:37
  • 1
    "Cannot reference a field before it is defined"?
    – K.Nicholas
    Apr 29, 2018 at 21:35
2
public class Main {
    static class Wrapper {
        Function<Integer, Integer> f;
    }

    public static void main(String[] args) {
        final Wrapper w = new Wrapper();
        w.f = x -> x == 0 ? 1 : x * w.f.apply(x - 1);
        System.out.println(w.f.apply(10));
    }
}
2

A bit like the very first reply ...

public static Function<Integer,Double> factorial;

static {
    factorial = n -> {
        assert n >= 0;
        return (n == 0) ? 1.0 : n * factorial.apply(n - 1);
    };
}
1
  • 3
    All of the replies are basically the same. But why does Java require you to declare the Function as an instance or class variable? Why does it not allow you to just declare it in your method??? Jul 28, 2014 at 11:39
2

You can define generic Fixed-point combinator like this.

public static <T, R> Function<T, R> fixedPointCombinator(Function<Function<T, R>, Function<T, R>> f) {
    return new Function<T, R>() {
        @Override
        public R apply(T n) {
            return f.apply(this).apply(n);
        }
    };
}

And

Function<Function<Integer, Double>, Function<Integer, Double>> fact =
    self -> n -> n == 0 ? 1 : n * self.apply(n - 1);

System.out.println(fixedPointCombinator(fact).apply(10));

output:

3628800.0
2
  • 2
    Thanks, I hate it. Sep 13, 2020 at 16:49
  • @EthanMcCue, Updated my answer.
    – user4910279
    Feb 19, 2021 at 22:14
2

The following works but it does seem arcane.

import java.util.function.Function;

class Recursion{

    Function<Integer,Integer>  factorial_lambda; // The positions of the lambda declaration and initialization must be as is.

    public static void main(String[] args) {new Recursion();}

    public Recursion() {
        factorial_lambda=(i)->{
            if(i==1)
                return 1;
            else
                return i*(factorial_lambda.apply(i-1));
        };
        System.out.println(factorial_lambda.apply(5));
     }
}

// Output 120
1

I heard at the JAX this year, that "lambads do not support recursion". What is meant with this statement is that the "this" inside the lambda always refer to the surrounding class.

But I managed to define - at least how I understand the term "recursion" - a recursive lambda and it goes like that:

interface FacInterface {
  int fac(int i);
}
public class Recursion {
  static FacInterface f;
  public static void main(String[] args)
  {
    int j = (args.length == 1) ? new Integer(args[0]) : 10;
    f = (i) -> { if ( i == 1) return 1;
      else return i*f.fac( i-1 ); };
    System.out.println( j+ "! = " + f.fac(j));
  }
}

Save this inside a file "Recursion.java" and with the two commands "javac Recursion.java" and "java Recursion" it worked for me.

The clou is to keep the interface that the lambda has to implement as a field variable in the surrounding class. The lambda can refer to that field and the field will not be implicitly final.

1

You can also define it as a local variable by creating a final array of size one (of say Function[]) and then assign the function to element 0. Let me know if you need the exact syntax

1

Given the fact that "this" in the lambda refers to the containing class, the following compiles with no errors (with added dependencies, of course):

public class MyClass {
    Function<Map, CustomStruct> sourceToStruct = source -> {
        CustomStruct result;
        Object value;

        for (String key : source.keySet()) {
            value = source.get(key);

            if (value instanceof Map) {
                value = this.sourceToStruct.apply((Map) value);
            }

            result.setValue(key, value);
        }

        return result;
    };
}
1

Another recursive factorial with Java 8

public static int factorial(int i) {
    final UnaryOperator<Integer> func = x -> x == 0 ? 1 : x * factorial(x - 1);
    return func.apply(i);
}
1
  • 1
    Nice solution, though I don't see why you would't use recursive methods without lambdas if you resort to methods anyways. Oct 18, 2017 at 11:25
1

@IanRobertson Nicely done, in fact you can move the static 'factory' into the body of the interface itself thus encapsulating it entirely:

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

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

This is the cleanest solution/answer I have seen so far ... especially since the invocation of "fact" is written "naturally": fac.apply(n) which is what you would expect to see for a unary function like fac()

0

The problem, is that lambda-functions want to operate on final variables, while we need a mutable Function-reference that can be replaced with our lambda.

The easiest trick, appears to be to, to define the variable as a member variable, and the compiler won't complain.

I changed my example to use IntUnaryOperator instead of IntToDoubleFunction, since we're just operating on Integers anyway here.

import org.junit.Test;
import java.util.function.IntUnaryOperator;
import static org.junit.Assert.assertEquals;

public class RecursiveTest {
    private IntUnaryOperator operator;

    @Test
    public void factorialOfFive(){
        IntUnaryOperator factorial = factorial();
        assertEquals(factorial.applyAsInt(5), 120); // passes
    }

    public IntUnaryOperator factorial() {
        return operator = x -> (x == 0) ? 1 : x * operator.applyAsInt(x - 1);
    }
}
0

Here is a solution that does not rely on a side effect. To make the purpose interesting, let's say that you want to abstract over the recursion (otherwise the instance field solution is perfectly valid). The trick is to use an anonymous class to get the 'this' reference:

public static IntToLongFunction reduce(int zeroCase, LongBinaryOperator reduce) {
  return new Object() {
    IntToLongFunction f = x -> x == 0
                               ? zeroCase
                               : reduce.applyAsLong(x, this.f.applyAsLong(x - 1));
  }.f;
}

public static void main(String[] args) {
  IntToLongFunction fact = reduce(1, (a, b) -> a * b);
  IntToLongFunction sum = reduce(0, (a, b) -> a + b);
  System.out.println(fact.applyAsLong(5)); // 120
  System.out.println(sum.applyAsLong(5)); // 15
}
1
  • this is cool, because the inner function does not even have to be a lambda field. It can be a method which you can access with ::f
    – lue
    Oct 1, 2020 at 12:22
0

You can create a recursive function using this class:

public class Recursive<I> {
    private Recursive() {

    }
    private I i;
    public static <I> I of(Function<RecursiveSupplier<I>, I> f) {
        Recursive<I> rec = new Recursive<>();
        RecursiveSupplier<I> sup = new RecursiveSupplier<>();
        rec.i = f.apply(sup);
        sup.i = rec.i;
        return rec.i;
    }
    public static class RecursiveSupplier<I> {
        private I i;
        public I call() {
            return i;
        }
    }
}

And then you can use any functional interface in just 1 line using a lambda and the definition of your functional interface like the following:

Function<Integer, Integer> factorial = Recursive.of(recursive ->
        x -> x == 0 ? 1 : x * recursive.call().apply(x - 1));
System.out.println(factorial.apply(5));

I found it very intuitive and easy to use.

0

Came accross this question during a lecture on Lambdas that used Fibonacci as a possible use case.

You can make a recursive lambda like this:

import java.util.function.Function;

public class Fib {

   static Function<Integer, Integer> fib;

   public static void main(String[] args) {
       fib = (n) -> { return n > 1 ? fib.apply(n-1) + fib.apply(n-2) : n; };

       for(int i = 0; i < 10; i++){
           System.out.println("fib(" + i + ") = " + fib.apply(i));
       }
   }
}

What do you have to keep in mind?

  • Lambdas are evaluated on execution -> they may be recursive

  • Using a lambda-variable inside of another lambda requires the variable to be initialized -> before defining a recursive lambda you must define it with a foo-value

  • using a local lambda-variable inside a lambda requires the variable to be final, thus it cannot be redefined -> use a class/ object variable for the lambda as it is initialized with a default value

0

Picking up on the common theme of answers here is that lambdas CAN be recursive, providing they have a fixed reference point (hence the class/interface based answers such as @assylias, @Andrey Morozov, @Ian Robertson, etc).

I really liked the answer from @000000000000000000000 with the member variable workaround but I have concerns if the intended lambda function wanted to reference other variables from the containing function's scope. Surely it'll be evaluating those local references at assignment and putting the resulting function into a member variable where it could be accessed by other methods in the class. That doesn't sound ... right (and could get quite interesting if the containing method itself is called recursively).

The following is a variation of the class-based solutions expressed in a form that's close to the OP's original one-line lambda but Eclipse doesn't complain about.

IntToDoubleFunction fact = new IntToDoubleFunction() {
    @Override
    public double applyAsDouble(int x) {
        return x == 0 ? 1 : x * this.applyAsDouble(x-1);
    }
};

The { } of course creates an anonymous class and thus a new scope with reference points for the lambda's evaluation with the added benefits of still being within containing function's own scope and thus "sibling" variables.

0

You could also define interface yourself wher you would just pass it itself as argument during call. E.g

interface MyOwnFunction<T,R>{
    R apply(MyOwnFunction<T,R> self,T arg);
}
0

A fixpoint operator Fix : ((S->T)->S->T)->S->T is an operator s.t. Fix(f) = f(Fix(f)). Here is a Java version using typecast from f : (S->T)->S-T into Fix(f) :S->T by a default method trick.

@FunctionalInterface
public static interface Fix<S, T> extends Function<S, T> {
    @Override
    public default T apply(S val) {
        return impl(this).apply(val);
    }

    public Function<S,T> impl(Function<S, T> rec);
}

public static void test() {
    Fix<Integer, Integer> fac = rec -> val -> val == 0 ? 1 : val * rec.apply(val - 1);
    System.out.println(fac.apply(10));
}
-3

I don't have a Java8 compiler handy, so can't test my answer. But will it work if you define the 'fact' variable to be final?

final IntToDoubleFunction fact = x -> {
    return  ( x == 0)?1:x* fact.applyAsDouble(x-1);
};
3
  • 1
    It does not. Maybe in Java 9 but not in Java 8. May 10, 2015 at 14:34
  • @ClaudeMartin Not possible in java >8. The problem is that the variable is not initialized, not that it can mutate.
    – lue
    Oct 1, 2020 at 12:14
  • Now it's 7 years later and no Java version allows this. fact is final but you still can't reference it from the lambda. Would be nice if they allowed it, as it certainly would be possible and is what people expect. Dec 19, 2022 at 15:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.