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 defs and dos 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 showing-off 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/3s. Instead, returning just the memo means that we can pipe the result through, rather than juggle four more variables.3

Bottom-Up -v- Top-Down

The examples above work top-down. They start at f(n), work their way through their definitions, till they bottom-out 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 base-case, f(0) and f(1), and make our way to the recursive case we want, f(n).3 A bottom-up approach. Let’s see what I mean in the trace below. We only ever need the two preceding Fibonacci terms to calculate the next:

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 two-dozen 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?