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...
