News

Embrace Recursion

Recursion is an essential tool in functional programming (FP) – it is the canonical way (and often the only way) to represent iteration.

Being a hybrid object/functional language, Scala offers both recursion and imperative control structures (like do, while, etc) to express iteration. However, imperative control statements imply using mutable state, while Scala (and FP in general) encourages data immutability. That is why you may prefer to use recursion (or higher order functions) in the first place.

To facilitate the FP approach to recursion, Scala offers:

So far so good. Yet the underlying platform (i.e. JVM) still uses up a call stack for non-tail recursive methods, so we can get a nasty stack overflow in no time while processing reasonably large amounts of data. Therefore it is a good idea to know where recursion lurks (and to easily distinguish its type).

While, in real-life code, recursion is not always obvious, new icons help us to reveal it:

Method with recursion icon

Let’s (for the sake of example) rewrite our linear recursion to tail recursion:

Method with tail recursion

We can use an intention (Alt + Enter) to automatically add @tailrec annotation which guarantees that compiler will always optimize the method (or will refuse to compile it).

An intention to add @tailrec annotation

After we (accidentally) change the method back to the linear recursion, we can immediately notice the violation of the contract:

Method with linear recursion annotated as @tailrec

If you wish, you may enable an optional “No @tailrec annotation inspection” which suggests to add @tailrec annotation when needed.