# Elixir - List Recursion

The first programming book I ever read was “Learn to Program” by Chris Pine. I remember making my first couple of interactive programs, and thinking, “Ok, this programming thing isn’t too bad”, and then about midway through the book. I got to the chapter on recursion and pretty much hit a wall. Recursion is a difficult concept to wrap your head around, and I consider it a rite of passage when I finally understand it in a new language.

In Elixir, recursion is usually explained along with lists, because they tend to work very nicely together. To get a better feel
for recursion and lists I tried my hand at creating my own implementations of Elixir’s `Enum`

module and so I think that might
be a good way to explain it below as well. Let’s dive in.

### Reduce

Map, Filter, and Reduce are some of the most important functions in programming many langauges. We won’t get into Map and Filter
but the majority of Enumeration functions in many languages can be implemented using Reduce. The concept of reduce is simple.
It takes a collection and, wait for it, *reduces* it down to one value. The thing that we want to explore is how this happens
recursively in lists.

Before jumping right into building our own reduce function lets start slow and first create something that can get the sum of
all of the elements in the following list: `[1, 3, 5, 9, 10]`

. As we will see, implementing sum will naturally lead us to an
implementation of reduce. We’ll start with a test of the simplest condition, an empty list.

```
defmodule RecursionExampleTest do
use ExUnit.Case
import RecursionExample
test "the sum of an empty list is 0" do
assert sum([]) == 0
end
end
```

We now write the simplest thing to make our test pass.

```
defmodule RecursionExample do
def sum(list) do
0
end
end
```

The second test, simply asserts that the sum of a list with one number is that number.

```
defmodule RecursionExampleTest do
use ExUnit.Case
import RecursionExample
test "the sum of an empty list is 0" do
assert sum([]) == 0
end
test "the sum of a list with one number is that number" do
assert sum([5]) == 5
end
end
```

This too, is easy to pass. We just write the simplest thing, and since Elixir supports the same function with mutiple bodies, we can just define another sum function that takes and returns what we need.

```
defmodule RecursionExample do
def sum([]), do: 0
def sum([n]), do: n
end
```

As you might expect, the next test adds another number to our list, and asserst that the sum of those two numbers is the sum of the list.

```
defmodule RecursionExampleTest do
use ExUnit.Case
import RecursionExample
test "the sum of an empty list is 0" do
assert sum([]) == 0
end
test "the sum of a list with one number is that number" do
assert sum([5]) == 5
end
test "the sum of a list with one number is that number" do
assert sum([5, 5]) == 10
end
end
```

The solution to this, is again writing another simple sum function with that takes and returns what we want. However, We can start to see that this approach will start to get cumbersome if our list grows any bigger.

```
defmodule RecursionExample do
def sum([]), do: 0
def sum([n]), do: n
def sum([x,y]), do: x + y
end
```

Our next test, tests what we actually want to test, and will force us to reconsider our design.

```
defmodule RecursionExampleTest do
use ExUnit.Case
import RecursionExample
test "the sum of an empty list is 0" do
assert sum([]) == 0
end
test "the sum of a list with one number is that number" do
assert sum([5]) == 5
end
test "the sum of a list with one number is that number" do
assert sum([5, 5]) == 10
assert sum([1, 3, 5, 9, 10]) == 28
end
end
```

Let’s start thinking about things in terms of lists. Lists can either be empty or have a head and tail which we can represent
like so: `list = [head | tail]`

. The tail of a list, is a list itself. So a list of 1 element like `list = [ 1 ]`

can actaully
be written as `list = [ 1 | [] ]`

. Pretty neat right? Now, if we think about our `sum`

function in these terms we can realize
what it is actually doing. It’s taking the head of the list, putting it somewhere, and calling `sum`

again with the tail of the
original list and adding that new head to the previous head. It does this all the way until the list is empty, at which point it
will return whatever the total is. That’s a lot to chew on. So let’s look at it in code.

```
defmodule RecursionExample do
def sum([], total), do: total
def sum([head | tail], total) do
sum(tail, head+total)
end
end
```

Wait, if we run this, our tests will still broken because our new sum functions take 2 parameters: a list and a total instead of just a list. Instead of changing all of our tests, we can simply refactor to something like this:

```
defmodule RecursionExample do
def sum(list), do: _sum(list, 0)
defp _sum([], total), do: total
defp _sum([h | t], total) do: _sum(t, h+total)
end
```

This is a pretty common pattern in Elixir. Define private helper methods (prefixed either with `_`

or `do_`

) that are invoked
by a public function. The prefix isn’t necessary it just makes that relationship explicit.

With that, we have finished created our generic `sum`

function. The next thing we might realize is that all sum, does is take
a collection, and return a single value - the sum of that collection. That’s exactly what reduce does! So let’s write some tests
for our reduce function in each of the test cases we used for our sum function. After all, they should be able to do the same thing.

Our sum function took a list and a accumulator, which we called `total`

our reduce function will need to take the same things
except it will also need a sum function that we can pass to it. Like our sum function this function will need to have 2 parameters
a list and an accumulator. Our reduce function starts to look like this

```
reduce([], acc, _), do: acc
reduce([head| tail], acc, function) do
reduce(tail, function.(head, acc), function)
end
```

The accumulator is just whatever is returned when we call the function with the head of the current list and current value of
the accumulator. To implement `sum`

we just need to add things together so we can pass in the anonymous function
`fn(x, y) -> x + y end`

which we can shorten using some syntactic sugar to `&(&1 + &2)`

. Thus we can now write out our test as:

```
defmodule RecursionExampleTest do
use ExUnit.Case
import RecursionExample
test "the sum of an empty list is 0" do
assert sum([]) == 0
assert reduce([], 0, &(&1 + &2) == 0
end
test "the sum of a list with one number is that number" do
assert sum([5]) == 5
assert reduce([5], 0, &(&1 + &2)) == 5
end
test "the sum of a list with one number is that number" do
assert sum([5, 5]) == 10
assert sum([1, 3, 5, 9, 10]) == 28
assert reduce([1, 3, 5, 9, 10], 0, &(&1 + &2)) == 28
end
end
```

And finally our reduce function as:

```
defmodule RecursionExample do
def reduce([], acc, _), do: value
def reduce([h | t], acc, func) do
reduce(tail, func.(head, acc), func)
end
def sum(list), do: _sum(list, 0)
defp _sum([], total), do: total
defp _sum([h | t], total) do: _sum(t, h+total)
```