A Dive into Recursion with Elixir

Today I was fortunate to join in on the Dockyard Academy for a discussion about Recursion.

We got a little thrown off the rails and luckily the inestimable Elixir guru Brooklin Myers showed up just in time to impart some key wisdom that I'll share with you today to keep you from falling into the same pit.

Recursion Analogy

We started the discussion with a review of recursion and the a quick analogy that I read about which explains tail-recursion vs body-recursion well intuitively.

Normal Recursion

Imagine you're reading a book (#1) and half-way through the book it references another book (#2). If you leave the current book unread and start to read the second book, that's like body-recursion because you have left the first book incomplete and you have to come back to it and finish. If you read about another book (#3) and leave book #2 unfinished to go read book #3 then you can see a stack forming. For the sake of completeness, you finish book #3, then return to book #2 to finish it, then return to book #1 to finish it.

Tail Recursion

Compare this with reading a book (#1) and seeing a reference to another book (#2) but you don't actually go read it until you finish the first book. Now you don't need to keep the first book sitting on your desk or remember where you were. This is similar to tail-recursion

Now to the Code

We chose a rather simple challenge - adding all the numbers in a list. In fact, this proved to be so simple that we did not see the performance characteristics we would expect to see as we compared a couple solutions. In this article, I'll add a second challenge to make the performance differences of various solutions more obvious.

Challenge - Add a list of numbers

Challenge

defmodule Recur do
  def add(list) do
    # return sum
  end
end

Recur.add([1,2,3,4,5]) 
# Expected to return 15

Normal Recursion Solution

  def add([]) do
    0
  end
  def add([head | tail]) do
    head + add(tail)
  end

I thought we could simply differentiate the tail vs normal recursion with the ordering of the arguments to the plus. This was an obvious oversight since the we want the add() to be called last, and with this code the plus was last.

A small change makes this much clearer, because we're effectively doing:

  def add([]) do
    0
  end
  def add([head | tail]) do
    tail_val = add(tail)
    head + tail_val
  end

In order to convert this to tail recursion, the plus operator needs to be applied on the way in, and we need to add an accumulator.

Tail Recursion Solution

  def add(list) do
    add(0, list)
  end
  def add(acc, []) do
    acc
  end
  def add(acc, [head | tail]) do
    add(acc + head, tail)
  end

I think of this as the plus getting applied on the way into the function instead of on the way out. And now the recursive call is the final line of the function.

Let's Benchmark it!

First here's the full code we'll benchmark, and I'll throw in a Reduce based solution for fun.

defmodule Recur do
  def addReduce(list) do
    Enum.reduce(list, 0, fn a, b -> a + b end)
  end
  def addTail(list) do
    addTail(0, list)
  end
  def addTail(acc, []) do
    acc
  end
  def addTail(acc, [head | tail]) do
    addTail(acc + head, tail)
  end
  def addBody([]) do
    0
  end
  def addBody([head | tail]) do
    addBody(tail) + head
  end
end

We'll use Benchee to run the tests a few times and measure both time and memory consumption.

Benchmarking code

list = Enum.to_list(1..100000000)

Benchee.run(
  %{
    "Tail" => fn -> Recur.addTail(list) end,
    "Body" => fn -> Recur.addBody(list) end,
    "Reduce" => fn -> Recur.addReduce(list) end
  },
  time: 10,
  memory_time: 2
)

Expectations

I expect that Tail would be slightly faster than Body, but with a much lower memory profile. I'm not sure what to expect with the Reduce - let's find out!

We see that Tail was actually significantly faster than Body. However, there was not much (any?) difference in memory usage which was unexpected.

Results

Name             ips        average  deviation         median         99th %
Tail            1.86      537.61 ms    ±26.29%      543.70 ms      825.98 ms
Reduce          1.74      573.97 ms    ±45.24%      456.07 ms     1184.55 ms
Body          0.0790    12659.51 ms     ±0.00%    12659.51 ms    12659.51 ms

Comparison: 
Tail            1.86
Reduce          1.74 - 1.07x slower +36.36 ms
Body          0.0790 - 23.55x slower +12121.90 ms

Memory usage statistics:

Name      Memory usage
Tail             552 B
Reduce           592 B - 1.07x memory usage +40 B
Body             552 B - 1.00x memory usage +0 B

The reason is that the challenge didn't show much difference in memory consumption was that the challenge itself is not memory intensive - we're just leaving a single integer on the stack.

We'll have to create a more memory intensive challenge for next time!