Tail Call Recursion in Java with ASM (2023)

Summary

One kind of optimization offered by some compilers is tail call optimization. This optimization does not bring much, since the programmer can always tailor his code without recursion, especially in an imperative language. On the other side, recursive code often times more elegant, so why we don’t let the compiler do the nasty stuff when it is possible? In this article I will present a neat way to implement tail call optimization in Java using byte code manipulation with ASM. What is tail call recursion? A tail call recursion is a special form of recursion where the last operation is the recursive call. It belongs to the more general class of tail calls, where the last operation is a method call. I will limit myself to the more restrictive case of tail recursion. Let’s illustrate with an example. long factorial(int n, long f) { if(n<2) { return f; } return factorial(n-1, f*n); } As one can see, the last operation is a call to the same function, but with different parameters. The next example is not a tail recursion. long factorial(int n) { if(n<2) { return f; } return n * factorial(n-1); } The reason why the previous example is not a tail call recursion is that the last operation is not the recursive call, but the multiplication operation. Multiplication happens after the recursive call returns. A tail recursion has a specific form which allows a faster execution by avoiding allocating a new stack frame since the execution can utilize the current stack. Anatomy of a method call If you don’t know much of how Java Virtual Machine make method calls this is a brief overview of it. The idea is almost universal in programming, however the details presented are specific to JVM. In order for a method to be able to execute it needs a space called frame, where some specific things should be contained: local variables space: a fixed array of entries with values of various types operand stack: a stack where the current operands are stored There is also an execution stack managed...