Scalæ By the Bay

Recursion is a fundamental building block of algorithmic design and a corner stone of many functional data structures. The Scala compiler has direct support for tail recursion and indirect support for mutually recursive function calls with a compiler plugin. So what makes a function recursive and what shape must it have to allow for tail call elimination? For that matter, what is tail call elimination? What does it mean to be mutually recursive? How does all this get translated into working, non-stack blowing code at compilation time? In this beginner-friendly look at all things recursion we’ll show how to take an imperative function and transform it into a recursive function. Through live code examples, attendees will see how to keep code referentially transparent without the need for external mutable variables while correctly handling state between “loops." Finally, we’ll introduce a new compiler plugin that adds mutual tail recursion and demonstrate how it can simplify complex, twisted logic.