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:
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… And there is nothing before zero to sum with, so how come we get the first 1? 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?”, an you answer 0 (zero). The first number of the sequence? 1.
The second? 1 as well.
The third? 2.
The fourth? 3.
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, conditionally return 0 if the first number as asked for, and 1 if the second number 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.
//
}|
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: