tailrec 🐈

Introduction

tailrec is a keyword which enables the optimization of tail recursive functions. A tail recursive function is defined by having a recursive call as its last executable statement. Instead of creating a new stack entry for each recursive call, functions marked as tailrec “reuse” the existing one. Therefore saving you from a possible stack overflow (if you would make a lot of recursive calls) and keeping your allocated memory lower. It is important to note that the JVM does not support proper tail recursion - Kotlin solves this by using trampolining (as we will see later).

A simple example:

tailrec fun factorialRegular(start: Int, accumulator: Int = 1): Int =
    if (start == 1) accumulator
    else factorialRegular(start - 1, accumulator * start)

Comparison to a regular recursive function

The previously shown function could be written without tailrec - like this:

fun factorialRegular(start: Int, accumulator: Int = 1): Int =
    if (start == 1) accumulator
    else factorialRegular(start - 1, accumulator * start)

To understand how the tailrec version is “reusing” the stack entry we must take a look at the bytecode decompiled to Java:

// regular version
public static final int factorialRegular(int start, int accumulator) {
    return start == 1 ? accumulator : factorialRegular(start - 1, accumulator * start);
}

The non-tailrec version is basically how you would write it in Java - there is nothing special here. Now let’s take a look at the tailrec version:

// tailrec version
public static final int factorialRegular(int start, int accumulator) {
    while(start != 1) {
        int var10000 = start - 1;
        accumulator *= start;
        start = var10000;
    }

    return accumulator;
}

This version eliminates recursion by wrapping everything in a while loop. This is - to my understanding - a form of trampolining (explained in the section Why doesn’t Kotlin support mutual tail recursion?). What’s interesting is how recursion is avoided:

//recursive call
factorial(start - 1, accumulator * start)

becomes

while(start != 1) {
    int var10000 = start - 1;
    accumulator *= start;
    start = var10000;
}

To keep it simple: tailrec just leads to a “rewrite” of the function from a recursive to an imperative manner.

More in depth

What I have already explained should be sufficient knowledge for day to day programming. However there are still some unanswered questions:

• Why doesn’t the compiler automatically optimize tailrec functions (without the need for the keyword)?
• Why has the return type (even for such a simple example like factorial calculation) be specified explicitly?
• Why doesn’t Java support tailrec?
• What is mutual tail recursion?
• Why doesn’t Kotlin support mutual tail recursion?

Why doesn’t the compiler automatically optimize tailrec functions?

I am just going to quote Roman Elizarov from the Jetbrains team:

Implicit tailrec optimization is very fragile and error-prone. People make mistakes and tailrec modifier is here to explicitly declare programmer’s intent to define a tailrec function. You (as a programmer) declare your intent and compiler verifies it. It also serves as a helpful piece of documentation for future readers and maintainers of your code. If they accidentally break it, they’ll get caught by compiler.

Why has the return type be specified explicitly?

One word: Speed.

With a more complicated type inference system the compiler could figure out the return type, but unfortunately this would cause the compilation process to be a lot slower.

Why doesn’t Java support tailrec?

I will reference directly to this question on the softwareengineering stackexchange: “Why doesn’t Java have optimization for tail-recursion at all?”.

The user ggovan gave a very concise answer:

As explained by Brian Goetz (Java Language Architect at Oracle) in this video: “In jdk classes […] there are a number of security sensitive methods that rely on counting stack frames between jdk library code and calling code to figure out who’s calling them”.

Anything that changed the number of frames on the stack would break this and would cause an error. He admits this was a stupid reason, and so the JDK developers have since replaced this mechanism. He further then mentions that it’s not a priority, but that tail recursion “will eventually get done”. N.B. This applies to HotSpot and the OpenJDK, other VMs may vary.

What is mutual tail recursion?

I really like the following explanation (for more in depth info you can visit the site):

Mutually tail-recursive functions are commonly encountered in practice. Assume that foo and bar are two mutually defined functions. In the body of either foo or bar, a tail-call to foo or bar is referred to as a mutually tail-recursive call. If every call to foo or bar in the bodies of foo and bar are tail-call, then foo and bar are mutually tail-recursive. Mutual recursion involving more functions can be defined similarly.

Why doesn’t Kotlin support mutual tail recursion?

Someone on SO asked exactly that. The answer given by comonad is a very good explanation in my opinion.

What you are looking for are “proper tail calls”. The JVM does not support those, so you need trampolines. A proper tail call cleans up the memory of its own function (parameters, local variables) before jumping (instead of calling) to the tail called function. That way the tail called function can return directly to its caller-caller-function.

Infinite mutual recursion is possible. (In functional languages this is one of the most important features.) To allow proper tail calls in assembler you would need a command to jump (goto) to a routine/method that is referred to via pointer. OOP needs calls (stores location to jump back to on the stack and then jumps) to a routine/method that is referred to via pointer.

You can emulate proper tail calls with the trampoline design pattern, maybe there is some support via library. The trampoline is a while loop that calls a function which returns a reference to the next function which returns a reference to the next…