Recursion

Recursion occurs when a method or function calls itself. The scary thing about this to the uninitiated is how easy it is to create an infinite loop that just goes round and round calling itself.

Once you get used to it recursion becomes really powerful and is an important part of the Scala programmer’s toolkit. It is especially useful when dealing with collections – part of functional programming is about avoid temporary variables such as those often found in for loops.

Recursion is not specific to functional programming but is used a great deal. For instance, the ‘Hello World’ of any functional programming language is the function ‘factorial’.

def factorial(n: Int): Int = n match {
  case 0 => 1
  case other => other * factorial(other - 1)
}

This is one of the simpler recursive methods, often a recursive function in Scala will have an outer and inner function – the outer one being the ‘public’ method creating initial values for the inner function, calling it and then returning the answer from it:

def length[A](seq: Seq[A]): Int = {
  @tailrec
  def _len(seqInner: Seq[A], n: Int = 0): Int = seqInner match {
    case Nil => n
    case head :: tail => _len(tail, n + 1)
  }
  _len(seq)
}

Here the outer function length just delegates to the inner function. The two main things to note in this example are the @tailrec annotation and the n parameter to the inner function.

The @tailrec annotation indicates that the developer assumes that the compiler will perform a certain optimization. If the compiler is unable to perform this it will produce a warning to make the developer aware. The optimization will be converting the call to a while loop behind the scenes. Tail recursion is a bigger topic than I can do justice and hopefully the subject of a subsequent post.

The n parameter has a default value meaning the outer function need not pass it but recursive calls may.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s