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.

About Pavel Fatin

IntelliJ Scala plugin developer (http://pavelfatin.com)
This entry was posted in Uncategorized. Bookmark the permalink.

6 Responses to Embrace Recursion

  1. bill says:

    I’m not seeing this in the latest version of the Scala plugin. What version of IDEA and the Scala plugin do I need to use this?

  2. kamre says:

    What about complex recursion with several methods involved? Will it also be detected?

  3. Looking forward to have tailrec labeling, looks great :)

  4. Értékelem azt a fantasztikus poszt , Én örülök megfigyelhető ez a website a yahoo.

  5. Wonderful beat ! I wish to apprentice while you amend your site, how
    could i subscribe for a blog site? The account aided me a acceptable deal.
    I had been a little bit acquainted of this your broadcast offered bright
    clear concept

    My website … san antonio carpet cleaning

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">