We can't find the internet
Attempting to reconnect
3 Ways To Fibonacci In Elixir
Introduction
About 10 years ago, when I was learning to code, I read a post listing five ways to code the Fibonacci Sequence in Python. I wrote more or less the same thing in Elixir a few years ago but never published it.1 Here’s a heavily revised version.
I consider the Fibonacci Sequence an analogue to the C classic, Hello World, but for Functional Programming. It’s one of the first things I code up when I come to a new language. Here’s its definition:
Of course, the formula isn’t what I want to show, it just helps to have it here for reference.
Plain & Simple
Our first version is as simple as we can get it.
defmodule Math.V1 do
def f(0), do: 0
def f(1), do: 1
def f(n) when n > 1, do: f(n  1) + f(n  2)
end
I was going to say it’s similar to the formula above but the def
s and do
s make me think again.
One thing is for sure, out of all the examples, it’s most clear what it does because it’s a translation of the formula into code directly.
There’s no how it does it to get in the way of clarity or obscure what it does.
To calculate a term (i.e. f(n)
) with V1
we have to compute the entire tree that grows out of f(n  1) + f(n  2)
.
Let’s see an example.
To calculate f(4)
we have to calculate f(4  1) = f(3)
and f(4  2) = f(2)
, to calculate f(3)
we have to calculate f(3  1) = f(2)
, and so on (see below).
In doing so, we repeat lots of the calculation, paying the same term a visit at different parts of the tree.
We end up calculating f(2)
twice:
f(4)
┣ f(3)
┃ ┣ f(2) ## 1st
┃ ┃ ┣ f(1)
┃ ┃ ┗ f(0)
┃ ┗ f(1)
┗ f(2) ## 2nd
┣ f(1)
┗ f(0)
The bigger the n
we pass to f(n)
, the bigger the tree, and the more the repetition.
How can we do better while showingoff some neat code in Elixir?
Don’t Repeat
As per the section title, we’ll store our calculations, so that we don’t repeat them. It was more challenging, and more fun, to write this memoized code than I thought it’d be. Here’s my code after a few attempts:
defmodule Math.V2 do
def f(n) when n >= 0 do
memo = %{0 => 0, 1 => 1}
memo
> f(n)
> Map.fetch!(n)
end
defp f(memo, n) when is_map_key(memo, n) do
memo
end
defp f(memo, n) do
memo
> f(n  1)
> f(n  2)
> then(&Map.put_new(&1, n, &1[n  1] + &1[n  2]))
end
end
In V2
we store Fibonacci terms that we’d calculate again and again in memo
.
It still bares a lot of resemblance to the formula: (1) the initial memo lists the initial terms for n = 0
and n = 1
, and (2) we can clearly see a variation of f(n  1) + f(n  2)
in f/2
.2
My first attempts at f/2
returned a tuple of {nth, memo}
for the nth
term and the memo, the result and the accumulator respectively, much like Elixir’s get_and_update/3
s.
Instead, returning just the memo means that we can pipe the result through, rather than juggle four more variables.3
BottomUp v TopDown
The examples above work topdown.
They start at f(n)
, work their way through their definitions, till they bottomout at f(1)
and f(0)
.
They start at a recursive case (f(n)
) and work their way to a base case (either f(0)
or f(1)
), before the stack unwinds, adding up the terms either side of the +
in f(n  1) + f(n  2)
.
A different approach is to start with a basecase, f(0)
and f(1)
, and make our way to the recursive case we want, f(n)
.3
A bottomup approach.
Let’s see what I mean in the trace below.
We only ever need the two preceding Fibonacci terms to calculate the next:
0, 1, ...The first two terms.
0, 1, 1, ... 0 + 1 = 1.
0, 1, 1, 2, ... 1 + 1 = 2.
0, 1, 1, 2, 3, ... 1 + 2 = 3.
0, 1, 1, 2, 3, 5, ... 2 + 3 = 5.
So, starting with the base terms of 0
and 1
, we can iterate our way to successive values in chunks of two terms at a time.
It’s important to see that in this version evaluation starts at the base cases of f(0)
and f(1)
building up to f(n)
, which is confusing, because our previous versions started evaluation at the recursive case f(n)
breaking it down with f(n  1)
s and f(n  2)
s (even though their definitions started with the base case).4
You can read more on Wikipedia. In Elixir:
defmodule Math.V3 do
def f(n) do
{0, 1}
> Stream.iterate(fn {a, b} > {b, a + b} end)
> Enum.at(n)
> then(fn {a, _} > a end)
end
end
V3
is most efficient but most cryptic in some ways.
It keeps the bare minimum of two terms in memory, but you can’t see much that resembles the formula.
It’s all about the how, i.e. this particular method for generating the sequence, so the what is lost but the method is revealed instead.
Conclusion
Considering all the interesting twists and turns in all these versions and others, this post could easily have been about twodozen variations on Fibonacci, or all the iterations it took to get to the code here. It’s a shame because nice code takes a lot of work, but we only see the end result in a post, we don’t experience the journey with the author. I’ve been tinkering with these on and off for what must total a few days over a few years. How to better share the journey?

↩
I wanted to use it to teach functional programming and Elixir syntax.

↩
In Elixir the syntax
f/2
means the function namedf
that consumes two arguments. The functions namedf
of arity 1 and 3,f/1
andf/3
, are different functions. 
↩
Dropping the result part and keeping just the accumulator could extend to other code too. Though higherorder functions that use an accumulator cover most of my daytoday needs.

↩
I mean that the definitions for the previous versions start with the base cases.
V1
listsdef f(0)
anddef f(1)
beforedef f(n)
.V2
lists the initial terms in the memo before callingf/2
for help. InV3
we don’t have that. The order it’s evaluated in can’t possibly be written in any other order than the way it’s listed.V1
could be listed differently, withdef f(n)
listed beforedef f(0)
anddef f(1)
, so that evaluation proceeds in the same order as it is declared for n > 1. Of course, evaluation order doesn’t have to follow definition order, but I think it can be confusing.