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 existing stack frame so that the execution could continue once it returns. We can demonstrate this with...