Implement recursive lambda function using Java 8

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.

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

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.

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.

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

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 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 fact = x -> x== 0? 1: x * MyFactorial.fact.apply(x - 1 );

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

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

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.

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

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

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

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.

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.

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

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;
    };
}

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

@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()

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

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

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
}

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.

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

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.

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

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