Pragmatic Scala

Tail Call Optimization (TCO)

Although many languages support recursion, some compilers go a step further to optimize recursive calls. As a general rule, they convert recursions into iterations as a way to avoid the stack overflow issue.

Iterations don’t face the stack overflow issue that recursions are prone to, but iterations aren’t as expressive. With the optimization, we can write highly expressive and intuitive recursive code and let the compiler transform recursions into safer iterations before runtime—see Structure and Interpretation of Computer Programs [AS96] by Abelson and Sussman. Not all recursions, however, can be transformed into iterations. Only recursions that have a special structure—tail recursions—enjoy this privilege. Let’s ...