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!
Top comments (0)