Recursive function call in Scala

Question

I am trying to write a recursive sum function as:

val sumRecursive = (list: List[Int]) => list match {
  case Nil => 0
  case x::xs => x + sumRecursive(xs)
}

It gives error:

Error:(16, 23) recursive value sumRecursive needs type case x::xs => x + sumRecursive(xs)

I understand that recursive function needs to declare their return type. But I am not sure how to do it in this code structure.

Answer 1

As it complains for the absence of an explicit type, you can provide it the same way you would specify a classical type (val a: Int = 5):

val sumRecursive: List[Int] => Int =
  list => list match {
    case Nil => 0
    case x::xs => x + sumRecursive(xs)
  }

which gives:

scala> sumRecursive(List(1, 2, 3))
res0: Int = 6

To perform the analogy with val a: Int = 5,

• a is sumRecursive
• Int is List[Int] => Int
• 5 is list => list match { case Nil => 0; case x::xs => x + sumRecursive(xs) }

Answer 2

Maybe a tail recursive function will be better if your list is too long.

val sumRecursive: (List[Int], Int) => Int =
    (list, acc) => list match {
      case Nil => acc
      case x :: xs => sumRecursive(xs, x + acc)
    }

Try this

call it like this:

sumRecursive(List(1, 2, 3, 4, 5), 0)

0 is the accumulator that will be incremented to hold the sum value

Answer 3

As it is asking for the type annotation, in Scala the recursive function are not able to infer the return type of the function so. That’s something we need to do in your case it will be the Int.

Just type annotate the method like this.

val sumRecursive :Int= (list: List[Int]) => list match {
case Nil => 0
case x::xs => x + sumRecursive(xs)}

How Int I think you want to know that. Suppose you have 3 elements in the list: 1,2,3

sunRecursive(list): Int

It will go into the case x::xs which means x is the head of the list and xs is the tail.

1st step So you do 1 + sumRecursive(xs) //xs=2, 3

2nd step 2+sumResursive(xs) //xs=3

3rd step 3 +sumResursive(xs) //xs=Nil

It will go into the first case and return 0.

So 3rd step willreturn 3+0 to the second step It will become2+3 and return to the 1st step It will become1+2+3 which is 6 and it will return 6

So the return type will be Int ultimately.