Tail recursive functions in Kotlin

Algorithms that would normally be written using loops are instead written as recursive functions with no risk of stack overflows.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
tailrec fun factorial(n: BigInteger, run: BigInteger = BigInteger.ONE): BigInteger {
    return if (n == BigInteger.ONE) run else factorial(n- BigInteger.ONE, run*n)
}

tailrec fun fibonacci(n: Int, a: BigInteger, b: BigInteger): BigInteger {
    return if (n == 0) a else fibonacci(n-1, b, a+b)
}

fun main(args: Array<String>) {
    println(factorial(BigInteger("42")))
    // 1405006117752879898543142606244511569936384000000000

    println(fibonacci(42, BigInteger.ZERO, BigInteger.ONE))
    // 267914296
}

When a function is marked with the tailrec modifier and meets the required form, the compiler optimises out the recursion, leaving behind a fast and efficient loop based version instead.

Updated: