With all of the images of the previous lesson firmly ingrained in your brain, let’s write a `sum`

function using recursion!

## Sketching the `sum`

function signature

Given a `List`

of integers, such as this one:

`val list = List(1, 2, 3, 4)`

let’s start tackling the problem in the usual way, by thinking, “Write the function signature first.”

What do we know about the `sum`

function we want to write? Well, we know a couple of things:

- It will take a list of integers as input
- Because it returns a sum of those integers, the function will return a single value, an
`Int`

Armed with only those two pieces of information, I can sketch the signature for a `sum`

function like this:

`def sum(list: List[Int]): Int = ???`

Note: For the purposes of this exercise I’m assuming that the integer values will be small, and the list size will also be small. That way we don’t have to worry about all of the

`Int`

s adding up to a`Long`

.

## The `sum`

function body

At this point a functional programmer will think of a “sum” algorithm as follows:

- If the
`sum`

function is given an empty list of integers, it should return`0`

. (Because the sum of nothing is zero.) - Otherwise, if the list is
*not*empty, the result of the function is the combination of (a) the value of its head element (`1`

, in this case), and (b) the sum of the remaining elements in the list (`2,3,4`

).

A slight restatement of that second sentence is:

“The sum of a list of integers is the sum of the

headelement, plus the sum of thetailelements."

As Eckhart Tolle is fond of saying, “That statement is true, is it not?”

(Yes, it is.)

Thinking about a `List`

in terms of its head and tail elements is a standard way of thinking when writing recursive functions.

Now that we have a little idea of how to *think* about the problem recursively, let’s see how to implement those sentences in Scala code.

## Implementing the first sentence in code

The first sentence above states:

If the

`sum`

function is given an empty list of integers, it should return`0`

.

Recursive Scala functions are often implemented using `match`

expressions. Using (a) that information and (b) remembering that an empty list contains only the `Nil`

element, you can start writing the body of the `sum`

function like this:

```
def sum(list: List[Int]): Int = list match {
case Nil => 0
```

This is a Scala way of saying, “If the `List`

is empty, return `0`

.” If you’re comfortable with `match`

expressions and the `List`

class, I think you’ll agree that this makes sense.

### Note 1: Using `return`

If you prefer using `return`

statements at this point in your programming career, you can write that code like this:

```
def sum(list: List[Int]): Int = list match {
case Nil => return 0
```

Because a pure function doesn’t “return” a value as much as it “evaluates” to a result, you’ll want to quickly drop `return`

from your vocabulary, but ... I also understand that using `return`

can help when you first start writing recursive functions.

### Note 2: Using if/then instead

You can also write this function using an if/then expression, but because *pattern matching* is such a big part of functional programming, I prefer `match`

expressions.

### Note 3: Can also use `List()`

Because `Nil`

is equivalent to `List()`

, you can also write that `case`

expression like this:

` case List() => 0`

However, most functional programmers use `Nil`

, and I’ll continue to use `Nil`

in this lesson.

## Implementing the second sentence in code

That `case`

expression is a Scala/FP implementation of the first sentence, so let’s move on to the second sentence.

The second sentence says, “If the list is *not* empty, the result of the algorithm is the combination of (a) the value of its head element, and (b) the sum of its tail elements.”

To split the list into head and tail components, I start writing the second `case`

expression like this:

`case head :: tail => ???`

If you know your `case`

expressions, you know that if `sum`

is given a list like `List(1,2,3,4)`

, this pattern has the result of assigning `head`

to the value `1`

, and assigning `tail`

the value `List(2,3,4)`

:

```
head = 1
tail = List(2,3,4)
```

(If you don’t know your

`case`

expressions, please refer to the match/case lessons in Chapter 3 of the Scala Cookbook.)

This `case`

expression is a start, but how do we finish it? Again I go back to the second sentence:

If the list is

notempty, the result of the algorithm is the combination of (a) the value of its head element, and (b) the sum of the tail elements.

The “value of its head element” is easy to add to the `case`

expression:

`case head :: tail => head ...`

But then what? As the sentence says, “the value of its head element, and the sum of the tail elements,” which tells us we’ll be adding *something* to `head`

:

`case head :: tail => head + ???`

What are we adding to `head`

? *The sum of the list’s tail elements.* Hmm, now how can we get the sum of a list of tail elements? How about this:

`case head :: tail => head + sum(tail)`

Whoa. That code is a straightforward implementation of the sentence, isn’t it?

(I’ll pause here to let that sink in.)

If you combine this new `case`

expression with the existing code, you get the following `sum`

function:

```
def sum(list: List[Int]): Int = list match {
case Nil => 0
case head :: tail => head + sum(tail)
}
```

And that is a recursive “sum the integers in a `List`

” function in Scala/FP. No `var`

’s, no `for`

loop.

## A note on those names

If you’re new to `case`

expressions, it’s important to note that the `head`

and `tail`

variable names in the second `case`

expression can be anything you want. I wrote it like this:

`case head :: tail => head + sum(tail)`

but I could have written this:

`case h :: t => h + sum(t)`

or this:

`case x :: xs => x + sum(xs)`

This last example uses variable names that are commonly used with FP, lists, and recursive programming. When working with a list, a single element is often referred to as `x`

, and multiple elements are referred to as `xs`

. It’s a way of indicating that `x`

is singular and `xs`

is plural, like referring to a single “pizza” or multiple “pizzas.” With lists, the head element is definitely singular, while the tail can contain one or more elements. I’ll generally use this naming convention in this book.

## Proof that `sum`

works

To demonstrate that `sum`

works, you can clone my RecursiveSum project on Github — which uses ScalaTest to test `sum`

— or you can copy the following source code that extends a Scala `App`

to test `sum`

:

```
object RecursiveSum extends App {
def sum(list: List[Int]): Int = list match {
case Nil => 0
case x :: xs => x + sum(xs)
}
val list = List(1, 2, 3, 4)
val sum = sum(list)
println(sum)
}
```

When you run this application you should see the output, `10`

. If so, congratulations on your first recursive function!

“That’s great,” you say, “but how exactly did that end up printing `10`

?”

To which I say, “Excellent question. Let’s dig into that!”