Scala: Recursive Summation on List

Question

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

Can anyone please explain the last line.

So where is the intermediate result being stored in xs.head + sum(xs.tail) and after the + is it providing a single element to be added?

Answer 1

The best way to explain recursion IMHO is to do it by going through it step by step and see what is actually happening. Another thing that helps is adding return statement, especially if you come from language like Java because it is more understandable what is happening.

Your function with return would looks like this:

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

In your case you have function that sums all integer in a list.

So lets imagine that you have called function using list with following values (1,2,3)

How will function behave?

First function call will look like this:

if(xs.isEmpty) // false - it has 3 elements (1,2,3)
   return 0 // skipped
else
   return 1 + sum((2,3)) // xs.head is changed with 1 and xs.tail is list with (2,3)

Second call is now with list (2,3):

if(xs.isEmpty) // false - it has 2 elements (2,3)
   return 0 // skipped
else
   return 2 + sum((3)) // xs.head is changed with 2 and xs.tail is list with (3)

Trird call is now with list (3):

if(xs.isEmpty) // false - it has 1 elements (3)
   return 0 // skipped
else
   return 3 + sum(()) // xs.head is changed with 3 and xs.tail is empty list now

Fourth call is with empty list:

 if(xs.isEmpty) // true
    return 0 // Recursion termination case triggered

So now we have our sum call stack looking something like this:

sum((1,2,3))   
   where sum = 1 + sum((2,3))   
       where sum = 2 + sum((3))   
          where sum = 3 + sum(())    
             where sum = 0

And we simply start returning values:

sum((1,2,3))   
       where sum = 1 + 5   
           where sum = 2 + 3  
              where sum = 3 + 0 

so we end up with sum((1,2,3)) = 6

That is why we don't need to store "intermediate result", because calculating sum starts from the end and rolls backwards.