Do it in Java 8: Recursive lambdas

Searching on the Internet about recursive lambdas, I found no relevant information. Only very old post talking about how to create recursive lambdas in ways that don't work with final version of Java8, or more recent (two years old only) post explaining this possibility had been remove from the JSR specification in October 2012, because “it was felt that there was too much work involved to be worth supporting a corner-case with a simple workaround.”

Although it might have been removed from the spec, it  is perfectly possible to create recursive lambdas. Lambdas are often used to create anonymous functions. This is not related to the fact that lambdas are implemented through anonymous classes. It is perfectly possible to create a named function, such as:

UnaryOperator<Integer> square = x -> x * x;

We may then apply this function as:

Integer x = square.apply(4);

If we want to create a recursive factorial function, we might want to write:

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

But this won't compile because we can't use factorial while it is being defined. The compiler complains that “Cannot reference a field before it is defined”.

One possible solution is to first declare the field, and then initialize it later, in the constructor, or in an initializer:

UnaryOperator<Long> factorial;
{
  factorial = i -> i == 0 
      ? 1 
      : i * factorial.apply( i - 1 );
}

This works, but it is not very nice. There is however a much simpler way. Just add this. before the name of the function, as in:

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

Not only this works, but it even allows making the reference final:

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

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

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

Interesting things to note:

This function will silently produce an arithmetic overflow for factorial(26), producing a negative result.

It will produce 0 for factorial(66) and over, until around 3000, where is will overflow the stack since recursion is implemented on the stack. If you try to find the exact limit, you may be surprised to see that it sometimes happens and sometimes not, for the same values. Try the following example:

public class Test {

  static final UnaryOperator<Integer> count = x -> x  == 0
      ? 0
      : x + Test.count.apply(x - 1);

  public static void main(String[] args) {
    for (int i = 0;; i++) {
       System.out.println(i + ": " + count.apply(i));
    }
  }
}

Here's the kind of result you might get:

...
18668: 174256446
18669: 174275115
18670: 174293785
18671: 174312456
Exception in thread "main" java.lang.StackOverflowError

You could think that Java is able to handle 18671 level of recursion, but it is not. Try to call count(4000) and you will get a stack overflow. Obviously, Java is memoizing results on each loop execution, allowing to go much further than with a single call.

Of course, it is possible to push the limits much beyond by implementing recursion on the heap through the use of trampolining.

Another interesting point is that the same function implemented as a method uses much less stack space:

static int count(int x) {
  return x == 0
      ? 0
      : x + count(x - 1);
}

This method overflows the stack only around count(6200).