Fibonacci Sequence

Intro to the Fibonacci sequence

For these examples, we are going to use the sequence that includes the zeroth element as in OEIS A000045.

The Fibonacci sequence is a series of numbers. The next number in the sequence is the sum of its previous two numbers. Here’s a sample of the sequence, starting at 0:

\[[0, 1, 1, 2, 3, 5, 8, 13, 21, ...]\]

For example, how do we get to 8? Sum 5 and 3 (the two numbers before 8 in the sequence).

How do we get to 5? Sum 3 and 2 (the two numbers before 5 in the sequence).

How do we get 3? Sum 2 and 1 (the two numbers before 3 in the sequence).

How do we get 2? Sum 1 and 1 (the two numbers before 2 in the sequence).

How do we get 1 (the second 1 in the sequence)? Sum 1 and 0 (the two numbers before 1 in the sequence).

How do we get the first 1? Sum 0 and… Oops. There is nothing before zero to sum with, so how come we get the first 1? Or even 0? We don’t.

It is defined that the first two numbers in the Fibonacci sequence are 0 and 1, and then, the remaining numbers in the sequence can be determined by following the rule:

The next number in the Fibonacci sequence is the sum the two numbers that came before.

Algorithm to determine the nth number of the Fibonacci sequence

I ask you, “What is the zeroth number of the Fibonacci sequence?”, and you answer: “Zero.” The first number of the sequence? “One”.

The second? “One” as well.

The third? “Two.”

The fourth? “Three.”

And so on and so forth.

But because the first two numbers of the sequence are defined to be 0 and 1, an algorithm to produce the first and second numbers of the sequence does not apply the logic of adding the two numbers before, but simply returns 0 if the zeroth number of the sequence as asked for, and 1 if the first number of the sequence is asked for.

So, we could have an initial implementation covering those cases like this:

function fib(n) {
  if (n === 0)
    return 0;

  if (n === 1)
    return 1;

  //
  // If n > 2, then we can start applying the addition
  // rule of the two numbers that come before.
  //
}

And those are the two base cases we need to handle the specific cases. The remainder of the algorithm follows the “add the two numbers that come before” logic.

On code style

The conditionals can be simplified an many different ways, depending on the programming language. The goal here is to show the logic. Readers may make the code more performant, concise or elegant in any way that suits their styles and preferences.

Sum the previous two numbers

Let’s visualize the sequence this way: the first row are the Fibonacci numbers, the second row is the index or position (starting at 1 as we say things “what is the first number of the sequence”):

fib:  0   1   1   2   3   5   8   13   21   34   55   89   ...

idx:  0   1   2   3   4   5   6    7    8    9   10   11   ...

So what is the 9th number of the sequence? The answer is 34 as that is the sum of 21 and 13, which are the numbers at position 8 and 7.

And the algorithm can be something like this:

\[\begin{cases} f_{0} = 0 \\ f_{1} = 1 \\ f_{n} = f_{n - 1} + f_{n - 2} \end{cases}\]

function fib(n) {
  if (n === 0)
     return 0;

  if (n === 1)
     return 1;

  return fib(n - 1) + fib(n - 2);

Improving the conditionals

Just as an example, we can use an or and compact the two base cases to a single return:

if (n === 0 || n === 1)
  return n;

Or return n if \(n \le 1\).

if (n <= 1)
  return n;

And even using includes() or a similar function (depending on the language):

if ([0, 1].includes(n))
  return n;

As can see, some implementation approaches follow the algorithm logic more closely, while some others feel a bit more clever to make the code shorter and appear to deviate from the algorithm logic. But they all get the same result in the end.

Of course, the [0, 1].includes(n) creates an array, which is more costly than some other approaches, as there is more memory and garbage collection in involved, which also depends on the language being used.

Final, complete implementation

Here’s one complete final implementation that sounds reasonable to me:

/**
 * Returns the nth number of the Fibonacci sequence.
 *
 * NOTE: This implementation includes the zeroth element
 * as in https://oeis.org/A000045.
 *
 * ASSUME: `n >= 0`.
 *
 * @param {number} n Which nth element of the sequence to return.
 * @returns {number} The nth element of the sequence.
 */
function fib(n) {
  if (n <= 1)
    return n;

  return fib(n - 1) + fib(n - 2);
}

Note how JSDoc is properly used to make it clear that we include the zeroth element and that we assume \(n \ge 0\), which implies the function doesn’t handle invalid input (garbage in, garbage out).