The use of tailrec keyword in Kotlin

The tailrec keyword makes tail recursion more efficient and keeps the function away from StackOverflowError exception.

First we need to understand tail recursion. There are basically two types of recursion.

1. Non-tail recursion

2. Tail recursion

Non-tail recursion

In non-tail recursion, the recursive function call is not the only last statement. After returning back, there is something left to evaluate.

 fun factorial(n: Int): BigInteger {
    if (n == 1) {
        return BigInteger.ONE
    }

    return n.toBigInteger() * factorial(n - 1)
}

Tail recursion

In tail recursion, the recursive function call is the only last statement. There is no need to keep record of the previous state.

fun factorial(n: Int, result: BigInteger): BigInteger {
    if (n == 1) {
        return result
    }

    return factorial(n - 1, result * n.toBigInteger())
}

The factorial() tail recursion function will get StackOverflowError exception for big input n (my be greater then 20000).

Kotlin provides a solution for avoiding this StackOverflowError exception. To add tailrec keyword before the function, makes it StackOverflowError free.

tailrec fun factorial(n: Int, result: BigInteger): BigInteger {
    if (n == 1) {
        return result
    }

    return factorial(n - 1, result * n.toBigInteger())
}