What is the Fibonacci series?

The Fibonacci series is a series of numbers in which each number is the sum of the two preceding numbers. (Starting with 0 and 1)

Example: 0,1,1,2,3,5,8,13…….

Where and how did it originate?

Though the sequence had been described in Indian mathematics long ago, it was Leonardo Fibonacci (an Italian mathematician) who introduced the sequence to Western European mathematics.

It was introduced as the solution to the rabbit population problem.

The following YouTube video explains the problem:

https://www.youtube.com/watch?v=sjQlW6cH3Ko

2 ways of making a program to generate the numbers in the Fibonacci series:

  1. Recursive approach:
  2. Dynamic Programming approach

Recursive Approach:

In this approach we use simple recursion to print the values of the Fibonacci series till the nth term.

The function returns the value of the nth Fibonacci number.

The recursive function is of the form : Fn = F(n-1) + F(n-2)

If n is 0 or 1 then it returns 0 or 1 respectively. (This is the base case)

The values of F(n-1) and F(n-2) are recursively calculated.

The program(in python) is as follows:

 n = int(input("Enter the number: "))
 def recsol(n):
     if n == 0:
         return 0
     elif n == 1:
         return 1
     else:
         return recsol(n-1) + recsol(n-2)
 fib = []
 for i in range(n):
     fib.append(recsol(i))
 print("Recursive solution : ",fib) 

The following recursion tree will help you understand this approach better:

Time Complexity: T(n) = T(n-1) + T(n-2) + O(1)

This roughly becomes O(2n). However, this is not a tight upper bound.

Dynamic Programming Approach:

Look carefully at the recursive tree. It is observed that a lot of the operations are getting repeated.

For example: F(3) is calculated twice, F(2) is calculated thrice.

The values of previous elements are repeatedly calculated and this increases the time complexity.

This can be avoided by storing the values of the Fibonacci numbers calculated so far, in an array.

The program (in python) is as follows:

n = int(input("Enter the number: ")) 

def dpsol():
   fib = [-1] * n
   fib[0] = 0
   fib[1] = 1
   for i in range(2,n):
       fib[i] = fib[i-1] + fib[i-2]

print("DP solution : ",dpsol())

Time Complexity: O(n)

Visits: 147

3 Replies to “Generating Fibonacci Series”

Leave a Reply

Your email address will not be published. Required fields are marked *