Tail Call Optimization

What is tail call optimization?

Consider the code you write to be a procedure and the generated bytecode that will eventually run to be a process. The factorialIterative() function is an iterative procedure and is compiled into and will run as an iterative process—no surprise there. Likewise, factorialRec() is a recursive procedure and is compiled into, and run as, a recursive process, exactly what we’d expect there as well. However, the real gain, as explained in Structure and Interpretation of Computer ProgramsHarold Abelson and Gerald Jay Sussman. Structure and Interpretation of Computer Programs. MIT Press, Cambridge, MA, 2nd, 1996, is when a recursive procedure can be compiled into an iterative process. This approach will bring the best of both worlds—the code can be expressed as recursion, but it can enjoy the runtime behavior of iterations. So, no stack overflow errors.

That’s intriguing—compiling recursion into iteration—that’s exactly what the tailrec annotation will instruct the Kotlin compiler to do. Let’s rewrite the factorialRec() function to make use of that technique.

Using tailrec

As a first step, we’ll annotate the function with the tailrec keyword.

tailrec fun factorialRec(n: Int): BigInteger =
  if (n <= 0) 1.toBigInteger() else n.toBigInteger() * factorialRec(n - 1)

Good try, but that doesn’t work—we need to take a few more steps.

120
recursivetail.kts:4:1: warning: a function is marked as tail-recursive
 but no tail calls are found
tailrec fun factorialRec(n: Int): BigInteger =
^
recursivetail.kts:5:56: warning: recursive call is not a tail call
  if (n <= 0) 1.toBigInteger() else n.toBigInteger() * factorialRec(n - 1)
                                                       ^

Kotlin is too polite here and gives a warning, but remember to treat warnings as errors as discussed in Sensible Warnings. If we try to run the function for large inputs, this version’s fate will be the same as the older version of factorialRec(), a runtime error. Kotlin will optimize recursion to iteration only when the call is in tail position. Let’s discuss that further.

Looking at the code n.toBigInteger() * factorialRec(n - 1), we may be tempted to think that factorialRec() is executed last, but it’s the multiplication operation that kicks in before the function call returns. This operation waits for a call to factorialRec() to finish, thus increasing the stack size on each recursive call. A tail call is where the recursive call is truly the last operation in the function. Let’s rewrite the function factorialRec() and rename it as factorial() along the way.