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,  numbers)) 
// Crashed pretty soon, around 7K

However, Kotlin supports an optimization called tail recursion. One...