Recursive lambdas in Java 8

Many Java programmers believe that is is not possible to create recursive lambdas. This is simply not true.

One question that comes back often about Java 8 lambdas is "Can they be recursive?". The most current answer is simply no, although one may find answers stating that lambdas were once made recursive while Java 8 was in development, but this feature has been removed before the final release.

Some may argue that since Java uses stack based recursion, we don’t need recursive lambdas, since we should not be using recursion at all. However, even without heap based recursion, we can still make efficient use of recursion, as long as the number of recursive steps remains low (typically under 2000). So it could be useful to be able to define recursive lambdas. And anyway, it’s fun!

The problem with anonymous lambda based functions

Lambdas are most often used to define anonymous functions. A recursive function must call itself. An anonymous lambda can’t call itself since it has no name, so it can’t be recursive. However, not all lambdas are anonymous.

Named lambda based functions

It is of course perfectly possible to name a lambda based function, so we may be tempted to write a recursive factorial function as:

Function<Integer, Integer> factorial = x -> x == 1
    ? x
    : x * factorial.apply(x - 1);

However, this will not work and will produce a compiler error:

Error:(14, 18) java: self-reference in initializer

This is exactly the same as writing:

int x = x + 10;

The problem here is that we are referencing a variable while initializing it. So it is not yet initialized. There is a solution to this problem. We just have to first declare the variable and later assign a value to it. The variable will be initialized with the default value (0 for an int, null for the factorial function). We can do this in a constructor, or at the moment we first need it (lazy initialization), but the simplest way is to use an initializer:

Function<Integer, Integer> factorial;
{
  factorial = x -> x == 1
      ? x
      : x * factorial.apply(x - 1);
}

If you need a static function, you may use a static initializer:

static Function<Integer, Integer> factorial;
static {
  factorial = x -> x == 1
      ? x
      : x * factorial.apply(x - 1);
}

The problem with this approach is that we can’t declare the factorial field final. FP programmers love to make everything immutable. Can we do this? Yes, we can! Just use the trick in the following example:

final Function<Integer, Integer> factorial = x -> x == 1
      ? x
      : x * this.factorial.apply(x - 1);

By adding this. in front of the function name, we can both declare it as final and initialize it at the same time. If you prefer a static function, just replace this with the name of the class:

static final Function<Integer, Integer> factorial = x -> x == 1
      ? x
      : x * MyClass.factorial.apply(x - 1);

Beware of stack based recursion

This function uses stack base recursion, which means that every recursive call will push the current state on the stack, which has a very limited size. (The actual size is implementation dependant.) As a result, this program will blow the stack (resulting in a StackOverflowError) if you call the function with a value higher than somewhere between 2000 an 3000. So you should not use this kind of recursion in production code unless you are sure that the number of nested calls remains low. By the way, this function will result in an arithmetic overflow for f(18).

What’s next

In a next post, we will see how to handle heap based recursion in order to be able to use recursion in production code.