Tail Recursion in JAVA 8

A tail-recursive function is just a function whose very the last action is a call to itself. Tail-Call Optimisation(TCO) lets us convert regular recursive calls into tail calls to make recursions practical for large inputs, which was earlier leading to stack overflow error in normal recursion scenario.

With Scala, making a tail recursive function is easy. The Scala compiler detects tail recursion and replaces it with a jump back to the beginning of the function, after updating the function parameters with the new values.

Java does not directly support TCO at the compiler level, but with the introduction of lambda expressions and functional interfaces in JAVA 8, we can implement this concept in a few lines of code.

STARTING WITH TAIL RECURSION CODE:

1.  We’ll use these two methods in the new recursive version to compute a factorial, the factorialTailRec() method.

public class Factorial{
    public static TailCall factorialTailRec(final int factorial, final int number) {
        if (number == 1)
            return TailCalls.done(factorial);
        else
            return call(() -> factorialTailRec(factorial * number, number - 1));
    }
}

When we call the factorialTailRec() method, it returns immediately with an instance of TailCall. The key idea here is that if we call the done() method, we signal the recursion’s termination. On the other hand, if we were to go through the call() method, we would be asking for the recursion to continue, but only after we step down from the current stack level.

2. Let’s look at the TailCall interface.

@FunctionalInterface
public interface TailCall {
    TailCall apply();
    default boolean isComplete() {
        return false;
    }
    default T result() {
        throw new Error("not implemented");
    }
    default T invoke() {
        return Stream.iterate(this, TailCall::apply)
                .filter(TailCall::isComplete)
                .findFirst()
                .get()
                .result();
    }
}

The isComplete() method simply returns a false value. It collaborates with the apply() method, which will return the next TailCall instance waiting for execution. The invoke() has to repeatedly iterate through the pending TailCall recursions until it reaches the end of the recursion. Then, it has to return the final result (available in the result() method of the terminal TailCall instance). To create a lazy list of pending TailCall instances, we use the Stream interface’s iterate() static method. This method takes an initial seed value and a generator. For the generator to return the next pending TailCall instance it can use the apply() method of the current TailCall.

3. Let us make our TailCalls Convenience Class.

public class TailCalls {
    public static  TailCall call(final TailCall nextCall) {
        return nextCall;
    }

    public static  TailCall done(final T value) {
        return new TailCall() {
            @Override
            public boolean isComplete() {
                return true;
            }

            @Override
            public T result() {
                return value;
            }

            @Override
            public TailCall apply() {
                throw new Error("not implemented");
            }
        };
    }
}

In this class we implement two static methods, call() and done(). The call() method simply receives a TailCall instance and passes it along.

In the done() method we return a specialized version of TailCall to indicate recursion’s termination. In this method, we wrap the received value into the specialized instance’s overridden result() method. The specialized version’s isComplete() will report the end of the recursion by returning a true value. Finally, the apply() method throws an exception because this method will never be called on this terminal implementation of TailCall, which signals the end of the recursion.

4. Let’s run the code.

System.out.println(Factorial.factorialTailRec(1, 20).invoke());

We seed the factorialTailRec() with an initial factorial value, 1 and the number 20. The result of this call is a TailCall instance and we call the invoke() method on it.

With Tail-Call Optimisation technique on hand, we can boldly implement recursive solutions, with a minor redesign to turn them into tail calls.

Reference: Functional Programming in JAVA by Venkat Subramaniam