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