A tender introduction to Elixir recursion
I can’t recall writing a recursive method in Ruby. I think that’s because I find recursion more confusion than iteration (ie Array#map
). Second, recursion isn’t efficient in an imperative language like Ruby.
While I find recursive functions a bit difficult to grok in any language, writing a recursive function in Elixir is a good exercise for 3 reasons:
- Unlike Ruby, there isn’t a performance hit when you use recursion in Elixir.
- Exposure to the inner workings of the
List
type. - Exposure to pattern matching in multiple ways.
I’ll start with some background on List
and pattern matching, then write a function to sum the contents of a List
. Finally, we’ll write a recursive map function.
Introducing the List
At first-glance, the Elixir List
type resembles the Ruby Array
class. An Elixir list ([1, 2, 3]
) looks like a Ruby Array
, doesn’t it?
Heads and Tails
However, a List
isn’t an ordered collection of values, like a Ruby Array
. A List
is a linked data structure. It has a head and a tail…just like this friendly snake:
The head contains a value (a String
, a Number
, etc). The tail? It contains another List
. So a List
is:
[head | tail]
The syntax below is — in fact — valid Elixir syntax:
iex(1)> [1 | [2] ]
[1, 2]
Look at the tail in the example above: [2]
. That is a List
with a head and tail too: [2 | []]
. So, we can represent this entire list as:
iex(2)> [1 | [2 | []]]
[1, 2]
…which would be an incredibly confusing way to write your List
, but it illustrates the core composition.
Pattern matching
A linked data structure is a key element of recursion in Elixir. The other? Pattern matching. We can easily grab the head and tail of a List
via pattern matching:
iex(7)> [head | tail] = [1,2,3]
[1, 2, 3]
iex(8)> head
1
iex(9)> tail
[2, 3]
In Elixir, the =
doesn’t indicate assignment. =
is a match operator. In short, how can make the left side of the equal the right side?
Sum a List
Let’s start our quick journey into Elixir recursion by summing the values of a List
.
Here’s the code:
defmodule MyList do
def sum([]), do: 0
def sum([head | tail]), do: head + sum(tail)
end
…but does it run?
iex(15)> MyList.sum([1,2,3])
6
Yes! What’s happening:
1. 1 + `sum([2,3])`
2. 1 + 2 + `sum([3])`
3. 1 + 2 + 3 + `sum([])`
4. 1 + 2 + 3 + 0
5. 6
If you are new to Elixir, the tricky part is likely the multiple function variants of sum/1
. Elixir doesn’t just pattern match on the left/right side of the =
operator. Elixir also implements pattern matching on function parameters: when an empty List
is passed to sum/1
, the first variant of sum/1
is matched and we return zero.
Map
Let’s take recursion one step further. Rather than returning a single value from a List
, we’ll return another List
. We’ll also generalize, letting us perform any operation on the data in the List
.
My function variants:
defmodule MyList do
def map([], _func), do: []
def map([head | tail], func), do: [func.(head) | map(tail, func)]
end
…and the output:
iex(19)>
iex(20)> MyList.map([“Dave”, “Chris”, “Josh”], fn(name) -> “Hello #{name}!” end)
[“Hello Dave!”, “Hello Chris!”, “Hello Josh!”]
What’s happening:
1. [ “Hello Dave!” | MyList.map([“Chris”, “Josh”], fn(name) -> “Hello #{name}!” end) ]
2. [ “Hello Dave!” | [ “Hello Chris!” | MyList.map([“Josh”], fn(name) -> “Hello #{name}!” end) ] ]
3. [ “Hello Dave!” | [ “Hello Chris!” | [“Hello Josh!” | MyList.map([], fn(name) -> “Hello #{name}!” end)] ] ]
4. [ “Hello Dave!” | [ “Hello Chris!” | [“Hello Josh!” | []] ] ]
5. [“Hello Dave!”, “Hello Chris!”, “Hello Josh!”]
Functions are a basic type in Elixir — in the above example, I passed a simple function to MyList.map/2
as the second argument, which is called by each value in the List
.
TL;DR
If you’re coming to Elixir from Ruby, it’s possible you haven’t touched recursion in a long while. It’s possible you still won’t touch recursion when using Elixir (see the Enum
module). However, Elixir does have first-class support for recursion and it is used frequently under-the-hood.