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.

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

[code lang=”java”]
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));
}
}
[/code]

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.

[code lang=”java”]
@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();
}
}
[/code]

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.

[code lang=”java”]
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”);
}
};
}
}
[/code]

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.

[code lang = “java”]
System.out.println(Factorial.factorialTailRec(1, 20).invoke());
[/code]

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.

Related posts:

In a world where most work goes online, the question then becomes, what behaviors do you emulate to advance yourself? What does this mean for internships? If we believe that life-long learning is…

I have always been interesting in writing in particular. But as I grow up psychologically, I started to see the activity underlying writing and other linguistic practical usage: constructing…

The only sound I can hear is the leaves rustling on the trees around me as I watch the sun setting behind the mountains, leaning on the wooden rail like I’m trying to get as close as humanly possible…