Summing values in a List

Solution 1:

Also you can avoid using recursion directly and use some basic abstractions instead:

val l = List(1, 3, 5, 11, -1, -3, -5)
l.foldLeft(0)(_ + _) // same as l.foldLeft(0)((a,b) => a + b)

foldLeft is as reduce() in python. Also there is foldRight which is also known as accumulate (e.g. in SICP).

Solution 2:

With recursion I often find it worthwhile to think about how you'd describe the process in English, as that often translates to code without too much complication. So...

"How do I calculate the sum of a list of integers recursively?"

"Well, what's the sum of a list, 3 :: restOfList?

"What's restOfList?

"It could be anything, you don't know. But remember, we're being recursive - and don't you have a function to calculate the sum of a list?"

"Oh right! Well then the sum would be 3 + sum(restOfList).

"That's right. But now your only problem is that every sum is defined in terms of another call to sum(), so you'll never be able to get an actual value out. You'll need some sort of base case that everything will actually reach, and that you can provide a value for."

"Hmm, you're right." Thinks...

"Well, since your lists are getting shorter and shorter, what's the shortest possible list?"

"The empty list?"

"Right! And what's the sum of an empty list of ints?"

"Zero - I get it now. So putting it together, the sum of an empty list is zero, and the sum of any other list is its first element added to the sum of the rest of it.

And indeed, the code could read almost exactly like that last sentence:

def sumList(xs: List[Int]) = {
    if (xs.isEmpty) 0
    else xs.head + sumList(xs.tail)
}

(The pattern matching versions, such as that proposed by Kim Stebel, are essentially identical to this, they just express the conditions in a more "functional" way.)

Solution 3:

Here's the the "standard" recursive approach:

def sum(xs: List[Int]): Int = {
  xs match {
    case x :: tail => x + sum(tail) // if there is an element, add it to the sum of the tail
    case Nil => 0 // if there are no elements, then the sum is 0
  }
}

And, here's a tail-recursive function. It will be more efficient than a non-tail-recursive function because the compiler turns it into a while loop that doesn't require pushing a new frame on the stack for every recursive call:

def sum(xs: List[Int]): Int = {
  @tailrec
  def inner(xs: List[Int], accum: Int): Int = {
    xs match {
      case x :: tail => inner(tail, accum + x)
      case Nil => accum
    }
  }
  inner(xs, 0)
}