Recursion

Recursion is a function invoking itself with new arguments. Many well-known algorithms, such as depth-first search, rely on recursion.

Here is an example of a very inefficient function that uses recursion to calculate the sum of all the numbers in a given list:

fun sumRec(i: Int, sum: Long, numbers: List<Int>): Long {
    return if (i == numbers.size) {
        return sum
    } else {
        sumRec(i+1, numbers[i] + sum, numbers)
    }
}

We often try to avoid recursion due to the stack overflow errors that we may receive if our call stack is too deep. You can call this function with a list that contains a million numbers to demonstrate this:

val numbers = List(1_000_000) {it}
println(sumRec(0, 0, numbers))
// Crashed pretty soon, around 7K

However, Kotlin supports an optimization called tail recursion. One of the great benefits of tail recursion is that it avoids the dreaded stack overflow exception. If there is only a single recursive call in...