Not able to write a method in Tail Recursion in Scala

Question

I have a function:

@tailrec
def sampleTailRec(list: List[Int]) : List[Int] = {
  if(list.nonEmpty) {
    val value: Int = list.head * 2
    List(value) ++ sampleTailRec(list.drop(1))
  } else {
    List()
  }
}

which is giving me following Compile error

could not optimize @tailrec annotated method sampleTailRec: it contains a recursive call not in tail position List(value) ++ sampleTailRec(list.drop(1))

I had tried to write code in Tail Recursion

Not able to understand why is my code not in Tail Recursion & how to make this method tail recursive?

Answer 1

Your method sampleTailRec is not tail recursive.

A method is tail recursive only if the recursive call is the last thing that happens before the method returns. That is not the case in your method. Look at this line:

List(value) ++ sampleTailRec(list.drop(1))

Think about what happens when this line is executed:

• First, list.drop(1) is evaluated
• Then the method is called recursively: sampleTailRec(list.drop(1))
• Then the result of that is appended to List(value)

Note that there is a step that is executed after the recursive call - the result of the recursive call is used to determine the final result.

Answer 2

Tail-recursive calls do not modify (or use) the results of the recursive call in any subsequent operations. Your example does as it prepends List(value). This inhibits the optimization. Often you can achieve tail recursion by passing more state down through the call.

Answer 3

If my understanding is right, you are trying to multiply each element in the list by 2, take a look at this:

$ scala
Welcome to Scala version 2.10.4 (Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_05).
Type in expressions to have them evaluated.
Type :help for more information.

scala>   @scala.annotation.tailrec
     |   def sampleTailRec(list: List[Int], accumulator: List[Int] = List.empty[Int]) : List[Int] = {
     |     list match {
     |       case Nil => accumulator.reverse
     |       case head :: Nil => sampleTailRec(Nil, head * 2 :: accumulator)
     |       case head :: tail => sampleTailRec(tail, head * 2 :: accumulator)
     |     }
     |   }
sampleTailRec: (list: List[Int], accumulator: List[Int])List[Int]

scala> sampleTailRec(1 to 10 toList)
warning: there were 1 feature warning(s); re-run with -feature for details
res0: List[Int] = List(2, 4, 6, 8, 10, 12, 14, 16, 18, 20)

Answer 4

You can convert your method to the following one, which uses tail-recursion in the way you intend, and has the same (linear) complexity :

def sampleTailRec(list:List[Int]): List[Int] = {
  @tailrec
  def sampleTailRec_aux(l: List[Int], result: List[Int]): List[Int] = {
   if (l.nonEmpty) sampleTailRec_aux(l.tail, (l.head * 2) :: result)
   else result.reverse
  }
  sampleTailRec_aux(list, List())
}