Tail recursion in Java
… or how to benefit from annotation processing in a cooler thing than the builder example.
Forewords
Tail recursion is a compile-level optimization that is aimed to avoid stack overflow when calling a recursive method. For example, the following implementation of Fibonacci numbers is recursive without being tail-recursive.
The Scala compiler has a built-in tail recursion optimization feature, but Java’s one doesn’t. In this short article, we are going to see how annotation processing could be used to bring tail recursion in the Java world.
The algorithm
… explained in Python.
The following Python snippet explains how we fake tail recursion. We have written it using decorators, which is a Python feature that allows some preprocessing just before the final interpretation.
As you see, the trick is to replace the decorated Python method by some proxy acting as a method (= implementing the __call__ method). This proxy catches the first call and encloses it in an endless while-loop. Every subsequent method call will either return a secret token, or the final result of the method.
In this pythonic version, we took benefit of
- The idea that a Python method can be proxied by an object (a method being, in fact, an object)
- The fact that a Python method has undeclared return type, making it possible to return either the “real final value”, or an arbitrary token
- The decoration feature of Python, which evaluates code before runtime evaluation itself.
All those features are impossible in Java:
- A method cannot be proxied as such: method is a method, not an object
- A method as typed return type and the used trick is not usable as such
- Java has no preprocessing feature (unlike Python or C/C++ for example)
We answered the above issues via Java-specific answers:
- if the recursive method is a (non-static) method in a class, inheritance can be used as a cheap proxy (around-advice in AOP terms).
- if the recursive call is signed as returning
Object, we can manage the token-trick. This is not a blocking feature, as a tail recursive call is always the last operation to be performed. - Java compiler has built-in annotation processor API, which can be used to generate code. This generation, although, is explicit and not hidden in the usual compilation flow.
Designing a tail recursive algorithm
The following snippet shows how we are going to design a tail-recursive algorithm:
As you see, we begin by defining an interface. Why not a class? Because what we are designing is an algorithm. As such, it is only a method contract which cannot have any relevant state. From the OOP point of view, what we are designing could hardly be an Object.
The recursive call needs to have return type as Object . This is a requirement which the user will not find blocking, as a tail recursive call is design to be a terminal operation. The exposed casting is done safely in the executor-method, which acts as a guard.
The whole interface is annotated as TailRecDiretive and the provided name is the name of the algorithm implementation that will be generated by our annotation processor.
The public guard (which is aimed to be used by users) is the TailRecursiveExecutor , while the recursive call is the TailRecursive method.
Note that we you have written here is a complete tail recursive algorithm. No boiler plate is needed, except the annotations. Those are mandatory, as the processor needs to know which method has which role, etc.
Processing the class
Letting our annotation processor run allows us to auto-generate a class Fibo in the same package as the FiboDirective . The class is an implementation of FiboDirective with an internal state that keeps tracks of the recursive execution process.
The important thing to note is that the TailReursivec call has been overwritten to throw an exception. This is to prevent misuage of the recursive alorithm: only the guard should be called.
The inner class (public with private constructor) makes use of the MethodHandle API from Java7, which is a low-power-fast-performing complement to the reflection API. (Reflection operations have all be performed during annotation processing, before compile time.)
Testing the result
The test cases for Fibonacci have been derived from the explicit mathematical formula of it:
The computation of the 1000 000th Fibonacci number takes around 15.5 seconds, which is completely comparable with Scala built-in execution time for the same algorithm.
This is because the main overhead of the above algorithm is not the tail recursive trap itself, but the usage of BigInteger computations. We guess that for smaller iterations, or less complex structures, built-in solutions as the one provided by Scala should be better than our.
Afterwords
In this short page, we’ve shown how to take benefit from annotation processing to fake tail recursion in Java.
Other approaches to tail recursion are possible, but our is the one that offers the less boiler plated code at write-time: you do not need a complex documentation about which kind of functional interface to instantiate, which weird proxy you need to call, … Things here are rather straightforward and consist of three annotations, one configuration line (for the name of the resulting class), and one caution about the return type of the recursive call (a misusage brings annotation-processing error anyway).
Recursivity is an important feature to have in many situations, in graph theory algorithms for example. Having tail recursion is a plus that worth it.
Further readings:
- https://github.com/Judekeyser/tail_rec for the Github project holding Java code. There is also an associated gist for more explanations and an old version of the code using AOP and Thread-based storing approach.
- https://github.com/Judekeyser/tail_recursive for the Github project holding Python code… although I don’t see any good reason to keep stuck there.
