Elixir foundations for Ruby Devs: Recursion

I can't recall writing a recursive method in Ruby. I think that's because I find recursion more confusing than iteration (ie Array#map). Additionally, 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:

  1. Unlike Ruby, there isn't a performance hit when you use recursion in Elixir.
  2. Exposure to the inner workings of the List type.
  3. 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.