Fibonacci Series in Python [Program with Explanation]

 

What is Fibonacci Series?

Once there lived a man in the Republic of Pisa named Leonardo Pisano Bogollo. He was the bravest mathematician among western countries. His nickname was Fibonacci which means “Son of Bonacci”. So, this series of numbers was named as Fibonacci Series. The Fibonacci Series is a never-ending Sequence where the next upcoming term is the addition of the previous two terms. The Fibonacci Series starts with 0,1…

Fibonacci Series: 0,1,1,2,3,5,8,13,21 and so on.

In the above example, you will observe that the series is starting with 0,1 and the third number is 1 because of the addition of the first two numbers is 1. The fourth number is 2 because the addition of the second and third number is 2 i.e 1+1=2. This sequence of addition goes on continuously. So, this sequence is called as Fibonacci Series.

Fibonacci Series Algorithm:

1st Step: Take an integer variable X, Y and Z

2nd Step: Set X=0 and Y=0.

3rd Step: Display X and Y.

4th Step: Z=X+Y.

5th Step: Display Z.

6th Step: Start X=Y, Y=Z.

7th Step: Repeat from 4-6, for n times.

Fibonacci Spiral

The Fibonacci Spiral is a type of spiral which is built by constructing the arcs which connect the points of the square by taking the help of the Fibonacci Sequence. These are assembled in spiral patterns.

There are different methods to print Fibonacci Series we will see that methods one by one.

Fibonacci Series in Python up to Certain Number

In this program, we will ask the user to enter the number up to which the user wants to print the series.

Python

1

#Learnprogramo

2

Number = int(input("How many terms? "))

3

# first two terms

4

First_Value, Second_Value = 0, 1

5

i = 0

6

if Number <= 0:

7

print("Please enter a positive integer")

8

elif Number == 1:

9

print("Fibonacci sequence upto",Number,":")

10

print(First_Value)

11

else:

12

print("Fibonacci sequence:")

13

while i < Number:

14

print(First_Value)

15

Next = First_Value + Second_Value

16

# update values

17

First_Value = Second_Value

18

Second_Value = Next

19

i += 1

Output:

In the above program, we’ve declared four variables i.e Number, First_Value, Second_Value, i.

Explanation:

Consider the value i=0, Number=5, First_Value=0, Second_Value=1.

1st Iteration: the while condition(0<5) returns TRUE so the while statement will start executing. We have used the if-else statement and condition if(0<=1) returns TRUE. So, Next=0 and then if statement block will exit. At last, i will increment.

2nd Iteration: the while condition(1<5) returns TRUE so the while statement will start executing. The condition if(1<=1) returns TRUE. So, Next=1 and then if statement block will exit. At last, i will increment to 1.

3rd Iteration: the while condition(2<5) returns TRUE and if(2<=1) returns FALSE so else statement will start executing. Next=First_Value+Second_Value=0+1=1 and the First_Value=Second_Value=1. So, Second_Value=Next=1 and i is incremented by 1.

4th Iteration: the while condition(3<5) returns TRUE and if(3<=1) returns FALSE so else statement will start executing. Next=First_Value+Second_Value=1+1=2 and the First_Value=Second_Value=1. So, Second_Value=Next=2 and i is incremented to 4.

5th Iteration: the while condition(4<5) returns TRUE and if(4<=1) returns FALSE so else statement will start executing. Next=First_Value+Second_Value=1+2=3 and the First_Value=Second_Value=2. So, Second_Value=Next=3 and i is incremented to 5.

6th Iteration: the while condition(5<5) returns FALSE and the program is exited. And the final output is 0 1 1 2 3.

Fibonacci Series in Python using Recursion

Recursion means calling the function itself directly or indirectly.

Python

1

def fibo_rec(n):

2

    if n == 1:

3

        return [0]

4

    elif n == 2:

5

        return [0,1]

6

    else:

7

        x = fibo_rec(n-1)

8

        # the new element the sum of the last two elements

9

        x.append(sum(x[:-3:-1]))

10

        return x

11

x=fibo_rec(5)

12

print(x)

Output:

Explanation:

In the above program, we use the recursion for generating the Fibonacci series. The function fibo_rec is called recursively until we get the proper output. In the program, we check whether the number n is 0 or 1. If yes then we return the value of the n and if not then we call fibo_rec with the values n-1 and n-2.

Using Dynamic Programming Approach

The Dynamic Programming Approach is nothing but similar to the divide and conquer method in the data structure. In this method, the problem is divided into smaller parts and their results can be reused. Generally, this approach is used for the optimization of the program.

Steps for Dynamic Approach:

• First initialize the array ar of size n to 0.
• if n=0 or 1 then return 1.
• else initialize ar[0] and ar[1] to 1.
• Now run the for loop in the range 2, n.
• Compute the value ar[i]=ar[i-1]+ar[i-2].
• Finally we get the array upto the sequence n.

Python

1

#Learnprogramo

2

ar = [0, 1]

3

def fibo(n):

4

  if n <= 0:

5

    print("Incorrect input")

6

  elif n <= len(ar):

7

    return ar[n - 1]

8

  else:

9

    temp = fibo(n - 1) + fibo(n - 2)

10

    ar.append(temp)

11

    return temp

12

print(fibo(9))

Output:

So, in this way we have learned the different methods to generate the Fibonacci Series in Python.