Convert sphere function to tail recursive function

Question

I have implemented Sphere function (takes a List of elements, squares every element and returns sum) in Scala. I want to convert this function to tail recursive. My code is here

def Sphere(list: List[Double]): Double = {
  val power = list.map(math.pow(_, 2))
  power.reduce(_+_)
}

Answer 1

It looks like:

  @tailrec
  def Sphere(list: List[Double], result: Double = 0): Double = list match {
    case Nil => result
    case x::xs => Sphere(xs, result + math.pow(x, 2))
  }

  println(Sphere(List(1,3,4,5)))

With @tailrec you make sure that it is actually tail recursive (the compile will fail).

Important is:

• that the last call is to itself
• that it has the intermediate result in the parameter list
• x is the head of the List where you do the calculation
• xs is the rest of the List (the tail) - where you append the recursive function on - until the List is empty > Nil.

Answer 2

If you want to keep the same function signature, you need to use a nested recursive function:

def Sphere(list: List[Double]): Double = {
  @annotation.tailrec
  def loop(rem: List[Double], res: Double): Double =
    rem match {
      case hd :: tail => loop(tail, res + hd*hd)
      case _ => res
    }

  loop(list, 0)
}

You can write this as a single tail-recursive function but that requires changing the function signature to add a spurious extra parameter. This is arguably bad design because the implementation is leaking out through the interface. This also requires the function to be marked final if it is a method.

Answer 3

Adding to the answers above, if you use foldLeft, it's already tail call optimised

def Sphere(list: List[Double]): Double = {
    list.foldLeft(0.0)((res, elem) => res + elem * elem)
}

It's better to use library versions and not add an extra check (@tailrec) for compiler when stuff's available.

**foldLeft is same as reduceLeft except that it takes an extra initial value as argument and not throw an exception when the collection is empty.

**foldLeft's actual implementation ends up using a while loop for performance reasons, but again that's the benefit of tail recursion, make it as fast as a loop.