What is tail recursion?

Kotlin is a multi-paradigm language. One of the paradigms that we can use is functional programming. In this post, we talk about recursion, a well known functional programming style, within the scope of Kotlin.

Loops and recursion

Loops are a concept that every software developer knows about. Using a traditional for loop or while loop allows us to do some repetitive task. Almost every language implements some kind of looping.

For this post, we will implement a factorial function in a few different styles. Lets initially take a look at a typical imperative approach:

fun factorial(num: Int): Long {
    var acc = 1
    for (x in 2..num ) {
        acc *= x
    }
    return acc
}

In the above example, we use a variable called acc which is mutated within a for loop. Our for loop iteratively calculates the factorial up to the number passed into our function before we eventually return.

When it comes to functional programming, we tend to avoid the use of loops. Instead, we use higher order functions (chaining) or recursion.

Recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem.

Using the same example, we now show the factorial function in a functional style using recursion:

fun factorial(num: Int): Long =
    if (num == 1) {
        1
    } else {
        num * factorial(num - 1)
    }

Given we pass 3 as our parameter, we would get the result 6. This leads to 3 calls to the factorial function. Each time we call the function, we must store the return location to the call stack, so that we can return to the first call and return the final value. If we were to pass a very large value to our factorial function, we will fall victim to a stack overflow.

We can avoid this stack overflow issue by using tail recursion.

Tail recursion

Tail recursion is an optimisation in which the tail operation (the last call a function makes to itself) returns directly to the original call site. In Koltin, this is done by applying the tailrec modifier to our recursive functions. However, to be eligible for tail recursion, we must ensure that our recursive function calls itself as its final operation.

We can adapt the function declared above such that the multiplication is not the last operation. We do this by passing the running result (accumulation) as an additional parameter.

tailrec fun factorial(num: Long, acc: Long = 1): Long {
    val factorial = num * acc
    return if (num <= 1) {
        factorial
    } else {
        factorial(num - 1, factorial)
    }
}

At compile time, our recursive function is optimised to use loops.

Below is the decompiled Java bytecode^[1]. We are now using a while loop. This means, we are free from the stack overflow issues that our previous functional recursion could have produced.

public static final long factorial(long num, long acc) {
    while(true) {
        long soFar = num * acc;
        if (num <= 1L) {
        return soFar;
        }

        long var10000 = num - 1L;
        acc = soFar;
        num = var10000;
    }
}

1. You can look at your Kotlin bytecode in IntelliJ by clicking on Tools > Kotlin > Show Kotlin Bytecode

   ↩