Implementing the Fibonacci Sequence in Python

Python is a powerful and versatile multi-purpose programming language that facilitates the implementation of Artificial Neural Networks and supports Natural Language Processing, Deep Learning, Facial Recognition, Genetic Algorithms, and many more such state-of-the-art AI-based tasks. 

This article explores some of the principal ways in which Python can be used to accurately generate the Fibonacci sequence – a great example of relatively simple algorithms that are not only useful in and of themselves but are often foundational to the building of advanced programs capable of complex cognitive functionalities.

What is the Fibonacci Sequence?

The Fibonacci Sequence is perhaps among the simplest, the earliest known, and the most famous of mathematical sequences known to mankind. 

It is a continuous series of whole number integers, where each successive number equals the sum of its preceding two numbers The Fibonacci Series starts with 0 and 1 and proceeds as follows: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368 and so on.

With zero as the starting point, the Fibonacci Sequence extends indefinitely in a bi-directional fashion as follows:
…610, -377, 233, -144, 89, -55, 34, -21, 13, -8, 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610… The sequence to the left of the zero is known as the “negafibonacci” sequence.

Check out our free technology courses to get an edge over the competition.

The Fibonacci sequence may be mathematically represented as follows:

Where n is the term number and xn is the term value. The formula to compute the term value xn is:
xn = xn-1 + xn-2 

So, the value of term number 8 for instance is: 

x8 = x7 + x6 

x8 = 13 + 8

x8  = 21

Here’s a bit of trivia related to the Fibonacci Sequence: Fibonacci Day is observed on November 23, as the date may be represented by the digits 1, 1, 2, and 3 – which represent a correctly sequenced segment of the Fibonacci Series of numbers. 

Explore our Popular Software Engineering Courses

History and Origins of the Fibonacci Sequence

Leonardo Pisano Bogollo, popularly known as Fibonacci, which in colloquial Italian parlance roughly translates to ‘son of Bonacci.’ 

Fibonacci was credited with the formulation of this special sequence of numbers, which – as a consequence – was named after him. He introduced it to a major part of western Europe at the start of the 13th century CE by way of his landmark book – Liber Abaci. 

Widely considered among the most talented mathematicians of his time, Fibonacci was, incidentally, also credited with the widespread adoption of the Hindu-Arabic numerals across all of Europe, which until then was using the far more cumbersome Roman numerals.

However, what is today called the Fibonacci Sequence, is now known to have been in use in ancient India as early as in the 3rd century BCE. 

It found expression in the Pingala-sutras, an ancient treatise of Sanskrit prosody, as well as in the Natya Shastra, a treatise on the ancient Indian performing arts, attributed to the revered sages of ancient India, Acharya Pingala and Bharata Muni, respectively. 

The most definitive commentary on the sequence appears in the work of Virahanka at the start of the 8th century CE. Though this text itself has not been traced, it has been referred to and extensively quoted in the work of Gopala in 1135 CE. Coincidentally, the digits of that year represent a consecutive sequence of Fibonacci numbers.

Another Indian Scholar of metrical rhythm, Acharya Hemachandra, is reputed to have had an intimate knowledge of the sequence, which he described in great detail in 1150 CE. This pre-dates Fibonacci’s work by over 50 years. 

Check Out upGrad’s Software Development Courses

Binet’s Formula

Like all constant-recursive sequences with constant coefficients, Fibonacci numbers can be shown as a closed-form expression that has come to be known as Binet’s formula. Named after Jacques Philippe Marie Binet, a prominent French mathematician from the early 19th century, Binet’s Formula can be represented as follows:

Given that Fn is the nth Fibonacci number:

What can be derived from the above formula is the fact that barring the first few numbers, the ratio between each consecutive pair of numbers in the Fibonacci series progressively converge upon what is referred to as the Golden Ratio – 1:1.618, denoted by the 21st letter of the Greek alphabet – Φ (phi).

This means that each number in the series is 0.6180339887 of the Fibonacci number that follows it OR that each successive number is 1.6180339887 times the number that precedes it in the Fibonacci sequence.

In-Demand Software Development Skills

The Fibonacci Sequence and the Golden Ratio

The significance of the Fibonacci Sequence and its derivative, the Golden ratio, is significantly heightened due to its uncannily frequent recurrence in nature. Some of the most common examples of this include:

• The number of petals on a flower is almost invariably a Fibonacci number, whether it’s the 3-petaled Lily, the 5-petalled Buttercup, the 21-petalled Chicory flower, or the 34-petalled Daisy.
  Intriguingly, this staunch conformity to Fibonacci numbers appears to be a product of Darwinian design, for scientists have found that these particular petal arrangements ensure that every one of these flowers gets optimal exposure to sunlight, moisture, and agents of pollination such as birds and insects. 
• The Golden ratio or Φ is seen in nearly all naturally occurring spiraling patterns – from seed heads of a Sunflower to entire galaxies, from protuberances on a pine cone to hurricanes, from spines on a Pineapple to the curvature of a goat’s horns, and from florets of a Cauliflower to the whorls on a human fingerprint.
  The spiraling pattern of a nautilus shell is considered a particularly iconic representation of what is called the ‘’Fibonacci Spiral”. 
• The branching of trees and root systems, the ratio between male and female bees in a beehive, various body parts of animals – from microbes to snails, turtles to whales, all conform to the Golden Ratio. 
• Aspects of human physiology – the ratio between our overall body length and the distance from our heads to our fingertips, for instance, or the ratio between the length of our forearms and our hands, are all designed in accordance to Φ.
  The Cochlea in the human ear is a Fibonacci Spiral, as is the umbilical cord. It is even believed that we are subconsciously drawn to faces whose height to width proportions approach the Golden Ratio. 

At its very essence, Mathematics is a quest to uncover patterns in all things. There is no better or more pervasive arena in which to seek out these patterns than in the lap of mother nature. 

From microorganisms to galaxies, the Fibonacci Sequence finds reflection in an overwhelming array of natural physiology as well as phenomena, from microscopic to cosmic in scale – and with good reason. 

The Golden Ratio or Φ confers an ergonomic balance of aesthetic and functional harmony to everything it finds expression in. It is for this reason that the Golden Ratio is also referred to as the Divine Proportion. 

But the significance of the Fibonacci Sequence extends well beyond the natural world, finding expression in a wide range of human endeavors – across mathematics, the sciences, and the arts. 

Read our Popular Articles related to Software

Generating the Fibonacci Sequence using Python

The Fibonacci Sequence and the Golden Ratio is integral to various aspects of:

• Algebra, geometry, statistics, and trigonometry – that can be applied to various economic practices and to stock market analysis.
• Biology, physics, and computer science – that finds application in synthetic biology and genetics, civil and mechanical engineering, architecture, interior design, and of course computer programming.
• Art and graphic design as well as poetry, music, and dance

It is often a fundamental step in the creation of a wide variety of useful applications linked to the above subjects and beyond.

The Fibonacci Sequence can be generated using a wide variety of programming languages. As stated earlier, Python is one of the most powerful and versatile of these – capable of using and manipulating Fibonacci Numbers and the Fibonacci Sequence in a number of ways in order to develop some of the most cutting-edge technology solutions. 

Check Out upGrad’s Advanced Certificate Programmer in Blockchain from IIIT Bangalore

Here are some of the methods by which Python can be used to generate the Fibonacci Sequence:

Iterative Approach

In this method, the algorithm:

• Assigns any two variables to represent the initial two consecutive terms within the sequence. Where 0 represents the first term of the sequence, and 1 represents the second.
• Sets the desired range of terms to be computed in the sequence and loop from 0 upwards.
• At each iteration, the algorithm: 
  • Adds the two variables. 
  • Then assigns the value of the second variable to the first variable
    and the sum of the previous two variables to the second variable.
  • And so on…

The corresponding code would be written as follows:

def fibo (num) : 

a = 0

b = 1

for i in xrange(0, 20):

print a

a, b = b, a + b

The corresponding output would be the first twenty numbers of the Fibonacci Sequence:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,
144, 233, 377, 610, 987, 1597, 2584, 4181

Recursive Approach

In this method, the algorithm derives: 

The value of each successive term by adding up the value of the preceding two terms. This may be represented as term n =  term n-1 + term n-2. 

The only two exceptions to this rule are when the value of the terms are 0 and 1, both of which return unchanged values. These exceptions can be represented as term n = term n.

The corresponding code would be written as follows:

def  recur_fodo (n):

if n  < =  1:

return n 

else:

return (recur_fibo (n-1) + recur_fibo (n-2) )

Nterms  = 20 

# check if the number of terms is valid

if nerms <= 0:

print (“Please enter a positive integer”)

else:

print (“Fibonacci sequence”)

For i in range (nterms):

Print (recur_fibo i)) 

The corresponding output would be the first twenty numbers of the Fibonacci Sequence:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,
144, 233, 377, 610, 987, 1597, 2584, 4181

Some stand-alone applications of Fibonacci Sequence

In addition to being a foundational step in the development of various complex models and applications, the Fibonacci Numbers, in and of themselves, possess some unique characteristics that render them invaluable in the performance of certain tasks:

• Fibonacci numbers may be used to analyze the computational runtime of Euclid’s algorithm to identify the largest common divisor of a random pair of integers, given the fact that a pair of successive Fibonacci numbers typically present the most severe challenge to this algorithm.
• Fibonacci numbers uniquely represent a complete sequence, such that each positive integer in the series is the sum of two Fibonacci numbers, any one of which can be used just once.
• Algorithms based on Fibonacci Numbers aided in the development of the Fibonacci search technique, the Fibonacci heap data structure, and the Fibonacci Cube Graphs used to interlink parallel and distributed systems.
• Fibonacci numbers are used in scrum poker – a consensus-based and gamified technique to estimate development goals in software development.
• The retracement of Fibonacci levels is commonly used in technical analysis for stock market trading.

In conclusion

We have, over the course of this article, attempted to pique your interest in the Fibonacci Sequence or the Golden Ratio – its key features and its astonishingly frequent recurrence in the natural world – both animate and inanimate.

We’ve tried to capture the impact and recreate the wonder that this mathematical phenomenon has created across a widely divergent and multidimensional gamut of human pursuits – the arts and sciences, engineering and technology, anatomy and genetics, economics and finance…and so much more.

We’ve attempted to bring to life how an extremely versatile programming language called Python can help you manipulate these mathematical concepts to benefit mankind in unexpectedly diverse ways – both directly and indirectly.

It is our fervent hope that this potent combination of Python and the Fibonacci Sequence has and will continue to capture your imagination, ignite your minds, fuel your aspirations and inspire you to the greatest heights of achievement. Happy coding! Happy dreaming!

At upGrad, we understand the importance of practical, hands-on learning – especially when it comes to software development. As a result, our courses and training initiatives have practicality at their very core. One such initiative is Full Stack Development Bootcamp which will help you develop all the relevant skills required to excel in full-stack development.