Tail recursive functions

Recursion is a powerful functional programming tool that most programmers have come across before. A recursive function is one that, when certain conditions are held, invokes itself. An idiomatic example of a recursive function is often the Fibonacci sequence, which, in English, is defined as follows—the next value is the sum of the previous two values.

In code, we can define Fibonacci as follows:

    fun fib(k: Int): Int = when (k) { 
      0 -> 1 
      1 -> 1 
      else -> fib(k - 1) + fib(k - 2) 
    } 

Notice that, for 0 and 1, we define the base case, which does not use recursion. However, for higher values, the function itself is called with the previous two values of k, and so on.

This is very succinct code, but it isn't the most efficient. Each time the fib function is invoked from within itself, the runtime must keep the...