Sums of different lists using recursion

Question

I am doing CodeWars challenges again and today I have a problem with this one:

Let us consider this example (array written in general format):

ls = [0, 1, 3, 6, 10]

Its following parts:

ls = [0, 1, 3, 6, 10]
ls = [1, 3, 6, 10]
ls = [3, 6, 10]
ls = [6, 10]
ls = [10]
ls = []

The corresponding sums are (put together in a list): [20, 20, 19, 16, 10, 0]

The function parts_sums (or its variants in other languages) will take as parameter a list ls and return a list of the sums of its parts as defined above.

object SumsOfParts {

  def partsSums(l: List[Int]): List[Int] = {

    var x: List[Int] = List()
    if (l.isEmpty)
      x
    else {
      x :+ l.sum
      partsSums(l.tail)
    }
  }
}

Here are the test samples:

partsSums(List(0, 1, 3, 6, 10)) should return List(20, 20, 19, 16, 10, 0) Test Failed

tail of empty list Stack Trace Completed in 4ms partsSums(List(1, 2, 3, 4, 5, 6)) should return List(21, 20, 18, 15, 11, 6, 0) Test Failed

tail of empty list Stack Trace partsSums(List(744125, 935, 407, 454, 430, 90, 144, 6710213, 889, 810, 2579358)) should return List(10037855, 9293730, 9292795, 9292388, 9291934, 9291504, 9291414, 9291270, 2581057, 2580168, 2579358, 0) Test Failed

tail of empty list Stack Trace Completed in 1ms partsSums(List(30350, 76431, 156228, 78043, 98977, 80169, 32457, 182875, 162323, 17508, 57971, 171907)) should return List(1145239, 1114889, 1038458, 882230, 804187, 705210, 625041, 592584, 409709, 247386, 229878, 171907, 0) Test Failed

Answer 1

You shouldn't use var in your recursive functions to pass state. You could fix your method like that:

def partsSums(l: List[Int]): List[Int] = {
    if (l.isEmpty)
      Nil //to finish recursion return empty list
    else {
      l.sum :: partsSums(l.tail) //prepend newly calculated sum to list returned by recursive call
    }
}

But this solution is naive since it recalculates sum on every iteration. We could make it better taking the previous sum from the head of the result and calculating the new sum by just adding it to the head of the list. I also use another list called acc to accumulate results, because this way I can make partsSums2 tail-recursive:

def partsSums2(l: List[Int], acc: List[Int] = List(0)): List[Int] = {
    if(l.isEmpty) {
      acc //at the end of recursion we return acc, which holds result
    } else {
      //acc.head is previos sum and l.head is value I want to add
      partsSums2(l.tail, (l.head + acc.head) :: acc)
    }
}

In order to make it work we also need to reverse list before passing to method:

SumsOfParts.partsSums2(List(0, 1, 3, 6, 10).reverse)

We need to reverse the list because the implementation of the immutable list in Scala is very affective on prepend operations (O(1)), but not on append operations (O(n)).

Finally you could just use scanRight:

def partsSums3(l: List[Int]): List[Int] = l.scanRight(0)(_ + _)

Answer 2

As @Andrey commented scanLeft solves this problem, but here is a recursive solution:

  def partsSums(l: List[Int]): List[Int] = {
    if (l.isEmpty) {
      Nil
    } else {

      def go(list: List[Int], acc: List[Int], currentSum: Int): List[Int] =

        list match {
          case Nil => (0 :: acc).reverse
          case x :: xs =>
            go(xs, currentSum :: acc, currentSum - x)
        }

      go(l, Nil, l.sum)
    }
  }

  def main(args: Array[String]): Unit = {
    println(partsSums(List(0, 1, 3, 6, 10)))
    // List(20, 20, 19, 16, 10, 0)
    println(partsSums(List(1, 2, 3, 4, 5, 6)))
    // List(21, 20, 18, 15, 11, 6, 0)
    println(partsSums(List(744125, 935, 407, 454, 430, 90, 144, 6710213, 889, 810, 2579358)))
    // List(10037855, 9293730, 9292795, 9292388, 9291934, 9291504, 9291414, 9291270, 2581057, 2580168, 2579358, 0)
    println(partsSums(List(30350, 76431, 156228, 78043, 98977, 80169, 32457, 182875, 162323, 17508, 57971, 171907)))
   // List(1145239, 1114889, 1038458, 882230, 804187, 705210, 625041, 592584, 409709, 247386, 229878, 171907, 0)
  }