54

I'm trying to write a scala function which will recursively sum the values in a list. Here is what I have so far :

  def sum(xs: List[Int]): Int = {
    val num = List(xs.head)   
    if(!xs.isEmpty) {
      sum(xs.tail)
    }
    0
   }

I dont know how to sum the individual Int values as part of the function. I am considering defining a new function within the function sum and have using a local variable which sums values as List is beuing iterated upon. But this seems like an imperative approach. Is there an alternative method ?

4
  • 47
    Doing the progfun course?
    – Noel M
    Commented Sep 19, 2012 at 14:40
  • 4
    Also note List.sum for when you don't need to write your own sum function.
    – Brian
    Commented Sep 19, 2012 at 17:26
  • 1
    please change the correct answer to list.sum as the title of your question is 'Summing values in a List'
    – pme
    Commented Feb 15, 2018 at 6:36
  • 1
    def sum(xs: List[Int]): Int = xs.reduce(_ + _)
    – SunilS
    Commented Apr 8, 2018 at 10:09

12 Answers 12

113

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).

1
  • Not sure in which version sum was added to TraversableOnce, now you could simply do as l.sum Commented Dec 20, 2018 at 16:11
80

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.)

1
  • 1
    Nice approach: simple, understandable, maintainable.
    – eddy147
    Commented Oct 29, 2016 at 7:15
66

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)
}
5
  • 9
    Reading Odersky's "Programming in Scala 2nd edition", it seems that Scala (now) detects tail-recursion automatically. @tailrec shouldn't be necessary. Quote: Functions which call themselves as their last action, are called tail recursive. The Scala compiler detects tail recursion and replaces it with a jump back to the beginning of the function, after updating the function parameters with the new values. (p 203). So as long as the last thing you do is calling yourself, it's automatically tail-recursive (ie. optimized).
    – kornfridge
    Commented Jan 10, 2013 at 11:16
  • In other words, your first code sample should be as efficient as the second.
    – kornfridge
    Commented Jan 10, 2013 at 11:19
  • 9
    @kornfridge, No, that is not correct. The first example, regardless of whether it has the annotation, is not tail-recursive since the last thing is does is add x to sum(tail); the second-to-last thing is does is make a recursive call to itself. See how that differs from the second example where the call to inner happens after the addition.
    – dhg
    Commented Jan 10, 2013 at 17:06
  • 12
    \@kornfridge, If i remember correct the @tailrec annotation at least checks that your function is tail recursive and generates an error otherwise. At least thats how i understood it.
    – sveri
    Commented Aug 8, 2013 at 10:32
  • 2
    @tailrec is for the compiler, it checks if the function can be run without keeping the stack frame alive after the recursive call. If it can't the compiler can tell you about it. Commented Apr 23, 2017 at 2:33
43

You cannot make it more easy :

val list  = List(3, 4, 12);
println(list.sum); // result will be 19

Hope it helps :)

2
  • What if the objects aren't numbers?
    – shinzou
    Commented Nov 7, 2017 at 10:56
  • 3
    If the objects aren't numbers you can map the values in the object that you'd like to sum. Example. You have a Sales Object. class Sales(type: String, amount: Int). Now you have a list of Sales. salesList: List[Sales]. To get the sum of sales. salesSum = salesList.map(_.amount).sum
    – alex
    Commented Mar 7, 2019 at 15:50
15

Your code is good but you don't need the temporary value num. In Scala [If] is an expression and returns a value, this will be returned as the value of the sum function. So your code will be refactored to:

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

}

If list is empty return 0 else you add the to the head number the rest of the list

1
  • hmm I just saw that @andrzej-doyle posted the same code before me Commented Sep 19, 2012 at 15:22
5

The canonical implementation with pattern matching:

def sum(xs:List[Int]) = xs match {
  case Nil => 0
  case x::xs => x + sum(xs)
}

This isn't tail recursive, but it's easy to understand.

3

Building heavily on @Kim's answer:

def sum(xs: List[Int]): Int = {
    if (xs.isEmpty) throw new IllegalArgumentException("Empty list provided for sum operation")
    def inner(xs: List[Int]): Int = {
      xs match {
        case Nil => 0
        case x :: tail => xs.head + inner(xs.tail)
      }
    }
    return inner(xs)
  }

The inner function is recursive and when an empty list is provided raise appropriate exception.

3

If you are required to write a recursive function using isEmpty, head and tail, and also throw exception in case empty list argument:

def sum(xs: List[Int]): Int = 
  if (xs.isEmpty) throw new IllegalArgumentException("sum of empty list") 
  else if (xs.tail.isEmpty) xs.head 
  else xs.head + sum(xs.tail)
1
 def sum(xs: List[Int]): Int = { 
  def loop(accum: Int, xs: List[Int]): Int = { 
    if (xs.isEmpty) accum
    else loop(accum + xs.head, xs.tail)
  }
  loop(0,xs)  
}
1
def sum(xs: List[Int]): Int = xs.sum

scala> sum(List(1,3,7,5))
res1: Int = 16

scala> sum(List())
res2: Int = 0
1
  • 1
    And how is this recursive, as the OP requested?
    – jwvh
    Commented May 29, 2017 at 7:12
1

To add another possible answer to this, here is a solution I came up with that is a slight variation of @jgaw's answer and uses the @tailrec annotation:

def sum(xs: List[Int]): Int = {
  if (xs.isEmpty) throw new Exception // May want to tailor this to either some sort of case class or do something else

  @tailrec
  def go(l: List[Int], acc: Int): Int = {
    if (l.tail == Nil) l.head + acc // If the current 'list' (current element in xs) does not have a tail (no more elements after), then we reached the end of the list.
    else go(l.tail, l.head + acc) // Iterate to the next, add on the current accumulation
  }

  go(xs, 0)
}

Quick note regarding the checks for an empty list being passed in; when programming functionally, it is preferred to not throw any exceptions and instead return something else (another value, function, case class, etc.) to handle errors elegantly and to keep flowing through the path of execution rather than stopping it via an Exception. I threw one in the example above since we're just looking at recursively summing items in a list.

0

Tried the following method without using substitution approach

def sum(xs: List[Int]) = {

  val listSize = xs.size

  def loop(a:Int,b:Int):Int={

    if(a==0||xs.isEmpty)
      b
    else
      loop(a-1,xs(a-1)+b)
  }

  loop(listSize,0)
}
3
  • There is no condition where xs.isEmpty at the same time as a != 0. The isEmpty test is redundant.
    – jwvh
    Commented Nov 25, 2016 at 7:50
  • If I send an empty list then the result should be 0. In this condition, the xs.isEmpty will be true. a == 0 will be true when the list loop has reached the first element. FYI, this has passed all the test cases in Coursera. Is there anything I misunderstood ? Commented Feb 23, 2017 at 15:36
  • If xs.isEmpty then a==0 is also true, it cannot be otherwise, so testing for the xs.isEmpty condition serves no purpose. In fact it adds unnecessary overhead. When summing a List of 1 million elements it will be called million-1 times. If you remove that test and only use if(a==0) you will always get the same result. Also, you don't need the listSize value. Invoking your loop like this loop(xs.size,0) is simple and easy to read and understand.
    – jwvh
    Commented Feb 23, 2017 at 17:32

Not the answer you're looking for? Browse other questions tagged or ask your own question.