How to create the Fibonacci sequence in Python

This tutorial is about Fibonacci sequence in which we will learn How to create the Fibonacci sequence in Python. First of all, lets what is a fibonacci sequence.

The Fibonacci sequence is the integer sequence of 0, 1, 1, 2, 3, 5, 8…. The first two terms are 0 and 1. All other terms are obtained by adding the preceding two terms. We can say that the nth term is the sum of (n-1)th and (n-2)th term. Mathematically:

If you want to learn more about Python Programming, visit Python Tutorials.

HOW TO IMPLEMENT THE FIBONACCI SEQUENCE IN PYTHON?

The Fibonacci sequence can be implemented using a variety of algorithms or techniques with different time complexities. Following are some of the common techniques to implement Fibonacci sequence:

• Iterative implementation of Fibonacci sequence
• Recursive implementation of Fibonacci sequence
• Fibonacci sequence using dynamic programming

Each method has its on time complexities. Lets discuss them one by one in detail.

Iterative implementation of fibonacci sequence

The iterative implementation is used for creating the Fibonacci sequence in python. It makes use of while or for loop. The program takes the term upto which you want the fibonacci series as an input. This term should be greater than 0.

Ending_No = int(input("Enter the numbers for the F-series  to go upto: "))

# first two terms
first_no, sec_no = 0, 1
count = 0

# Number entered should be a positive integer
if Ending_No<= 0:
   print("Warning..!!")
   print("Please enter a positive integer")

elif number == 1:
   print("Fibonacci sequence upto",number,":")
   print(n1)
#  fibonacci sequence upto entered number
else:
   print("Fibonacci sequence:")
   while count < Ending_No:
       print(n1, end=" ")
       nth = n1 + n2
       # Values are updating
       n1 = n2
       n2 = nth
       count += 1

Enter number of terms: 5
Fibonacci sequence:
0
1
1
2
3

In iterative implementation, we are iterating over the elements n times where n indicates the total number of terms in a fibonacci sequence. Therefore, the time complexity for iterative implementation of Fibonacci sequency is O(n).

Recursive Implementation of Fibonacci Sequence

Fibonacci Sequence can also be created using Recursive Implementation. Recursion is a problem solving technique in which we divide the problem into similar subproblems. Then call the same function directly or indirectly to solve them.

def Fibonacci(first, second, limit):

    #Terminate the code when the limit is reached
    if(limit == 0):
        return

    #Printing the next Fibonacci number.
    print(first + second, end=" ")

    Fibonacci(second, first+second, limit-1)

if __name__ == "__main__":
    #Printing first 2 values
    print(0,1,end=" ")

    #Calling the Fibonacci Function to print the remaining numbers 
    Fibonacci(0,1,7)

0 1 1 2 3 5 8

In case of recursive implementation, the time complexity in terms of Big O notation is exponential.

Fibonacci sequence using dynamic programming

In recursion, we solve similar subproblems multiple times. Dynamic programming, however, keeps track of previously resolved subproblems and avoids resolving them.  We have broken down the problem of fibonacci series into similar problems known as overlapping problems as shown in figure below. In this case, Fib(0), Fib(1) and Fib(2) are solved 2, 3 and 2 times. In dynamic programming, we’ll store their results and then use them to solve remaining subproblems.

def fibonacci_seq(num):
  #store the first two fixed terms in a list
    fib = [0, 1]
    for i in range(2, num+1):
        fib.append(fib[i-1] + fib[i-2])
    return fib

number=int(input("Enter the number of terms: "))    
res=fibonacci_seq(number)
print("Fibonacci sequence: ", res)

Enter the number of terms: 5
Fibonacci sequence:  [0, 1, 1, 2, 3, 5]On 

On executing the above program, you’ll get a fibonacci sequence in the form of a list. If you want to convert this list of numbers into a string, visit this link.