Photo by Alex Eckermann on Unsplash
Fibonacci series is one of the most common algorithms studied by beginner programmers, as it is a way to implement the recursion method in any of the most used programming languages.
Fibonacci series is nothing else than a sequence of numbers where the 𝑛𝑡ℎ term is the sum of the previous two terms in that series of numbers.
In mathematics, the Fibonacci numbers commonly denoted a 𝐹𝑛, form a sequence of numbers, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is:
𝐹0=0,𝐹1=1
and then,
𝐹𝑛\=𝐹𝑛−1+𝐹𝑛−2
This blog post does not pretend to be a complete detailed guide and study in regards to the generation and mathematical implications of this important series of numbers but does pretend to be a quick resume with history about this marvelous mathematical creation, for more detailed documentation Wikipedia has a nice article.
Brief History
The Fibonacci sequence appears in Indian mathematics in connection with Sanskrit prosody, in Pingala’s (c. 450 BC–200 BC) Sanskrit poetic tradition
Knowledge of the Fibonacci sequence was also by Bharata Muni on his Natya Shastra (c. 100 BC–c. 350 AD).
Outside India, the Fibonacci sequence first appears in the book Liber Abaci (The Book of Calculation, 1202) by Leonardo de Pisa, AKA Fibonacci, where this sequence was used to calculate the growth of rabbit populations.
Image from Getty Images
The enigma of rabbits
Nowadays, Fibonacci is better known for the discovery of some numbers, now called the Fibonacci sequence, which arose when he tried to solve an enigma about rabbit mating habits.
Suppose a farmer has a pair of rabbits.
Rabbits take two months to reach maturity, and after that, they give birth to another pair of rabbits every month.
The problem was how to know how many pairs of rabbits would have been in a given month.
Then:
- During the 1st month, you have a pair of rabbits and, as they have not matured, they can not reproduce.
- During the 2nd month, there is still a single pair.
- But at the beginning of the 3rd month, the first couple reproduces for the first time, so there are 2 pairs of rabbits.
- At the beginning of the 4th month, the first pair is reproduced again, but the second pair is not mature enough, so there are 3 pairs.
- In the 5th month, the first pair is reproduced and the second pair is played for the first time, but the third pair is still very young, so there are 5 pairs.
Image from BBC
The ritual of mating continues, but what you will notice soon is that the number of rabbit couples you have in a given month is the sum of the rabbit couples you have had in each of the two previous months, so the sequence continues, because in the illustration for the 5th month, will be able to mate, the yellow, green and purple pairs of rabbits, so the sequence continues with 8, and so on.
This sequence is expressed as:
1… 1… 2… 3… 5… 8… 13… 21… 34… 55… and so on.
Connection with nature and the golden ratio
Fibonacci numbers appear in nature often enough to prove that they reflect some naturally occurring patterns, for example, they appear in seed heads, pinecones, fruits, and vegetables. Even DNA molecules have the presence in some way of this series of numbers, a sample of this is that a single molecule measures 34 x 21 Angstroms in each complete cycle of the double helix spiral, which is the same as in the Fibonacci series, 34 and 21 successive numbers.
Image by Lean Moore
In arts and architecture, this “golden measure” also called the golden ratio was used to build the Great Pyramid of Giza and also used to define all the proportions in “Last Supper”, “Vitruvian Man” and “Mona Lisa”.
Image from Getty Images
Code to generate Fibonacci series
In the Python web site you can find one of the ways to generate the Fibonacci series by coding, find bellow this code in Jupyter notebook
Image from python.org
As an example of how this algorithm works, starting always with the pair of numbers 0, 1 defined by variables a, b, if the series goes until 5, it will always perform a sum of all the previous numbers on the series, like in the image below.
Image by author
The traditional way to generate the series in python starts by defining a function called fib, then inside of it, declaring the variables a, b equals to the first 2 numbers the series starts, 0 and 1. After that the code begins looping the numbers between a (means 0) and the value designed to n, in this case 10, so the initial pair of numbers: a which started as 0 becomes b (means 1), and the sum of a + b (means 0 + 1) = 1. This way the second pair of numbers is made 0, 1, 1...
Image by author
A very practical way to visualize step by step the execution of this code is pythontutor.com, find below a link that goes to the execution of the Fibonacci series in python
Image from pythontutor.com
Other ways to generate Fibonacci series
There are of course other different ways to get the same results in python, feel free to try these chunks of code by cloning the notebook from GitHub.
Image from author
The recursive way
Image by author
Using lists
Image by author
Through a loop
Image by author
Through this tutorial, we have learned a little bit of history regarding this basic but very important algorithm by visualizing its step-by-step execution and analyzing as well the primitive use case that helped us to know this method from its inception.
Cheers and happy coding!!