What is a recursive method?

A method that calls itself many times before reaching a specific condition or base case.

What is a tail-recursive method?

A method which calls itself in the last instruction (tail-call). In the case of Scala (and other FP languages), a tail-recursive method can reuse the stack frames in each iteration.

We can specify that a method has to be tail-recursive using the annotation @tailrec (if the implementation isn’t tail-recursive, the compiler shows an error).

In the following example, the tail-recursive method returns the last element of a list of Integers given by parameter:

  @tailrec
  def last(list: List[Int]):Int = list match {
    case List(x) => x
    case x::xs => last(xs)
  }

If the given list matches with a List of one element (List(x)) the method responds with that element, x.

In other case, if the list matches with a List of many elements composed by a head x and a tail xs, the method calls itself passing the tail by parameter.

What is this strategy good for?

The depth of the JVM call stack is limited; for this reason, if we have deep recursive calls it’s a good idea to use a method tail-recursive to reuse stack frames and avoid stack overflow errors.

On the other hand, if we don’t have the case mentioned before, it’s better not to use a recursive tail method and leave the code more easy to read.

goto Part III