The Fibonacci Sequence

Fibonacci numbers are named after the Italian mathematician Leonardo Pisano (Leonardo of Pisa, Italy). They are known to represent many natural phenomena such as how rabbits grow, how leaves branch, the structure of shells, and the formation of galaxies.

The Fibonacci numbers are described by the sequence 1,1,2,3,5,8… where each number (after the first two) is the sum of the two numbers preceding it. Thus 1+1=2 so 2 is the third number. 2+1=3 so 3 is the fourth number, and so on. The Fibonacci numbers go on forever.

Here is a simple Python program to generate Fibonacci numbers. The program is recursive in nature. The two base cases generate the first two Fibonacci numbers 1 and 1. The inductive step calls the function recursively to generate new numbers.Then in the main driver program, we use a for loop to print the first 25 Fibonacci numbers.

The result is:

Try changing 25 to a higher number, say 50. You will notice that the program gets really slow. Why? Why does it take so much time for Python to simply add numbers and print them in order? The reason is because the recursive calls repeatedly go all the way back to the first number numerous times for each repeated invocation of the function.

To address this inefficiency issue, we must do what is called “memoization”. Memoization is simply book-keeping, keeping a ready reference memory of previously computed numbers so you don’t keep recomputing them. Here is our new program:

We are now easily able to print the first 50 Fibonacci numbers:

The golden ratio is the number 1.618034… given by the solution to the equation x^2 = x + 1. It has a very interesting relationship to the Fibonacci sequence. The ratio of successive Fibonacci numbers approaches the golden ratio. Here’s a program to explore this connection.

This gives the output (last few lines shown):

Fibonacci numbers have a very interesting property. Take two adjacent Fibonacci numbers, e.g., 5 and 8. Note that 5 miles = 8 kilometers (approximately)! Wow! Let us take another example: 55 and 89. 55 miles is approximately 89 kilometers. The reason for this is because the conversion ratio between miles and kilometers is approximately the golden ratio.

Interested in more things Python? See our blogpost on Python's enumerate() capability. Also if you like Python+math content, see our blogpost on Magic Squares and our post on exploring multiples of 37 with Python. Finally, master the Python print function!

Want to learn Python with us? Sign up for 1:1 or small group classes.

What are Fibonacci numbers?

How can we write a Python program to generate Fibonacci numbers?

Is the above program efficient?

How can we improve our algorithm to generate Fibonacci numbers?

What is the golden ratio?

Using Fibonacci numbers to convert miles to kilometers