Embrace Recursion

Pavel Fatin

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:

• Immutable collections.
• Tail call optimization.

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:

Let’s (for the sake of example) rewrite our linear recursion to 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).

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

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