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.
What are Fibonacci numbers?
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.
How can we write a Python program to generate Fibonacci numbers?
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:
Is the above program efficient?
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.
How can we improve our algorithm to generate Fibonacci numbers?
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:
What is the golden ratio?
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):
Using Fibonacci numbers to convert miles to kilometers
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.
Kodeclik is an online coding academy for kids and teens to learn real world programming. Kids are introduced to coding in a fun and exciting way and are challeged to higher levels with engaging, high quality content.