Recursive Function & Tail call Optimization

A Recursive function on a large amount of data might overflow the Stack. Scala provides tail-call optimization on recursive functions(that meet certain criteria ; #PS:43). We can use annotation @tailrec to check if the compiler will perform the tail-call optimization on our Recursive Function.

Example 1 : A recursive function for which tail call optimization is not possible

Recursive call should be made in the last line of the recursive function in order to qualify for tail call optimization

scala> :paste
// Entering paste mode (ctrl-D to finish)

import scala.annotation.tailrec
@tailrec
final def sum(xs: List[Int]): Int = {
  xs match {
    case x :: tail => x + sum(tail)
    case Nil => 0
  }
}
// Exiting paste mode, now interpreting.

<console>:31: error: could not optimize @tailrec annotated method sum: it contains a recursive call not in tail position
         xs match {
         ^

Note : The need for using 'final' keyword is explained here

Example 2 : A recursive function for which tail call optimization is possible

Note : This is also an example for Nested Function ; in which we have nested our function(the recursive function) within another function

scala> :paste
// Entering paste mode (ctrl-D to finish)

import scala.annotation.tailrec
def mySum(data: List[Int]):Int = {
    //With @tailrec annotation, Compiler will throw an error, if
    //it is not possible to make tail-call optmization
    @tailrec
    def accumulate(data: List[Int], acc: Int):Int= {
        data match {
            case Nil => acc
            case x::tail => accumulate(tail, acc + x)
        }
    }
    accumulate(data, 0)
}

// Exiting paste mode, now interpreting.

import scala.annotation.tailrec
mySum: (data: List[Int])Int

scala> mySum(List(1, 2, 3, 4))
res4: Int = 10

Reference

http://alvinalexander.com/scala/scala-recursion-examples-recursive-programming