Kodeclik Blog

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.

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.

def fib(n):
  if (n==0) or (n==1):
    return(1)
  else:
    return fib(n-1)+fib(n-2)

for i in range(25):
  print(i+1,fib(i))

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:

memoized = {0: 1, 1: 1}

def fib(n):
  if (n in memoized):
    return(memoized[n])
  else:
    memoized[n] = fib(n-1) + fib(n-2)
    return(memoized[n])
  
for i in range(50):
  print(i+1,fib(i))

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

1 1
2 1
3 2
4 3
5 5
6 8
7 13
8 21
9 34
10 55
11 89
12 144
13 233
14 377
15 610
16 987
17 1597
18 2584
19 4181
20 6765
21 10946
22 17711
23 28657
24 46368
25 75025
26 121393
27 196418
28 317811
29 514229
30 832040
31 1346269
32 2178309
33 3524578
34 5702887
35 9227465
36 14930352
37 24157817
38 39088169
39 63245986
40 102334155
41 165580141
42 267914296
43 433494437
44 701408733
45 1134903170
46 1836311903
47 2971215073
48 4807526976
49 7778742049
50 12586269025

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.

memoized = {0: 1, 1: 1}

def fib(n):
  if (n in memoized):
    return(memoized[n])
  else:
    memoized[n] = fib(n-1) + fib(n-2)
    print("\t Golden ratio=",fib(n-1)/fib(n-2))
    return(memoized[n])
  
for i in range(50):
  print(i+1,fib(i))

This gives the output (last few lines shown):

….
     Golden ratio= 1.618033988749895
42 267914296
     Golden ratio= 1.618033988749895
43 433494437
     Golden ratio= 1.618033988749895
44 701408733
     Golden ratio= 1.618033988749895
45 1134903170
     Golden ratio= 1.618033988749895
46 1836311903
     Golden ratio= 1.618033988749895
47 2971215073
     Golden ratio= 1.618033988749895
48 4807526976
     Golden ratio= 1.618033988749895
49 7778742049
     Golden ratio= 1.618033988749895
50 12586269025

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.

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.