Python Program to Print the Fibonacci Sequence

Introduction

The Fibonacci series is a mathematical sequence of numbers in which, each element is the sum of the previous two elements. It starts with zero and one followed by 1, 2, 3, 5, 8, 13, 21, and so on. Each element in this sequence is called a Fibonacci number. In this article, we will see a Python program to print the Fibonacci series in Python.

It is a series of numbers that starts from 0 and 1 and then continues by adding the preceding two numbers. 

In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the function, 

  Fn = Fn-1 + Fn-2

With the initial two terms' values,

  F0 = 0 and F1 = 1

What is the Fibonacci Series in Python?

Fibonacci series is a sequence of numbers where starting from the third element, each element is the sum of the previous two elements. The Fibonacci series starts with 0 and 1. Therefore, the sequence is as follows: 0, 1, 1, 2, 3, 5, 8, 13, etc. The Fibonacci series has many interesting properties and is found in various aspects of mathematics.

There are many ways to generate a Fibonacci sequence containing N elements in Python.

Different Methods to Print Fibonacci Series in Python

• Method 1: Using Recursion
   
• Method 2: Using Dynamic Programming
   
• Method 3: Using While Loop
   
• Method 4: Cache

Method 1: Using Recursion

Recursion is the primary programming technique in which a function or algorithm calls itself directly or indirectly until a specified condition is met. Let’s see how to use recursion to print the first ‘n’ numbers of the Fibonacci Series in Python.

The function “fibonacciSeries” is called recursively until we get the output. We first check whether the Number is zero or one in the function. If yes, we return the value of the Number. If not, we recursively call Fibonacci with the values Number-1 and Number-2.

Implementation

# Python program to generate Fibonacci series Program using Recursion
def fibonacciSeries(Number):
	if Number == 0:
		return 0
	elif Number == 1:
		return 1
	else:
		return fibonacciSeries(Number - 1) + fibonacciSeries(Number - 2)


n = int(input())
print("Fibonacci series:", end=' ')
for n in range(0, n):
	print(fibonacciSeries(n), end=' ')

Input:

6

Output:

Fibonacci Series: 0 1 1 2 3 5

Recurrence Relation = T(n) = T(n-1) + T(n-2).

Time complexity 

The time complexity for this program is O(2ⁿ)

Space complexity

The space complexity for this program is O(n)

Method 2: Using Dynamic Programming

We can also use Dynamic Programming to print the Fibonacci Series in Python. The first two fixed values of the Fibonacci series are 0 and 1. We start our loop from the second index and try to append the values in the loop using the previous two numbers.

Implementation

# fibonacci series in python using dynamic programming
def fibonacci(n):
	# Taking 1st two fibonacci numbers as 0 and 1
	f = [0, 1]
	for i in range(2, n+1):
		f.append(f[i-1] + f[i-2])
	return f


n = int(input())
ans = fibonacci(n)
for n in range(0, n):
	print(ans[n], end=' ')

Input:

5

Output:

0 1 1 2 3

Time complexity 

The time complexity for this program is O(n)

Space complexity

The space complexity for this program is O(n)

Method 3: Using While Loop

The last approach we will be discussing is using a while loop. We will use some basic conditions to print the Fibonacci series. As we already know, the first two numbers of the Fibonacci series are 0 and 1 by default. Input the number of values we want to generate the Fibonacci sequence and initialize a=0, b=1, sum=0, and count=1. Start a while loop using the condition count<=n and print the sum every time the condition works. Increment the count variable, swap ‘a’ and ‘b,’ and store the addition of a and b in the sum. If count>n, the condition fails, and the algorithm ends.

Implementation

# Python program to generate Fibonacci series based on n value
n = int(input())
a = 0
b = 1
sum = a + b
count = 1
print("Fibonacci series is: ", end=" ")
while (count <= n):
	count += 1
	print(a, end=" ")
	a = b
	b = sum
	sum = a + b

Input:

3

Output:

Fibonacci series is:  0 1 1

Time complexity 

The time complexity for this program is O(n)

Space complexity

The space complexity for this program is O(1)

Method 4: Cache

In this code, a dictionary cache is used to store previously computed Fibonacci numbers so that they can be retrieved from the cache instead of being recomputed every time the function is called. When the function is called with a value of n, it first checks if the result has already been computed and stored in the cache. If it has, the cached value is returned. Otherwise, the function computes the Fibonacci number using the recursive formula fibonacci(n-1) + fibonacci(n-2), stores the result in the cache, and returns the result.

Implementation

cache = {}  # Cache to store previously computed Fibonacci numbers

def fibonacci(n):
	if n <= 1:
		return n
	elif n in cache:
		return cache[n]
	else:
		result = fibonacci(n-1) + fibonacci(n-2)
		cache[n] = result  # Store the result in cache for future use
		return result

n = int(input())
for i in range(0, n):
	print(fibonacci(i), end=' ')

Input:

3

Output:

0 1 1

Time complexity 

The time complexity for this program is O(n)

Space complexity

The space complexity for this program is O(n)

Also Read - Multilevel Inheritance in Python

Frequently Asked Questions

What is the Fibonacci series in Python?

It is a sequence of integers 0, 1, 1, 2, 3, 5... The series starts with 0 and 1. All other terms are obtained by adding the last two numbers of the sequence, i.e., to get the nth number, sum the (n-1)th and (n-2)th number.

How do you write a Fibonacci series program in Python?

You can write a Fibonacci series in Python through multiple methods, such as recursion, dynamic programming, and a while loop or For loop. First, define the base case for the first two values, 0 and 1. Then, add the last two values, and you will get the next integer in sequence.

How do you find the Fibonacci series in Python using for loop?

To find the Fibonacci Series in Python using for loop, we first initialise two numbers as 0 and 1. Then we use a loop to calculate and print the following numbers by adding the previous two.

How do you find the nth Fibonacci number in Python?

A Fibonacci series starts with 0 and 1. The later numbers are generated by adding the previous two values of the series. If n is 1 or 2, the answer would be 0 and 1, respectively. Otherwise, keep adding the last two Fibonacci numbers until you get the nth number.

Conclusion

This article discusses the different approaches to finding the Nth Fibonacci sequence using Python. You learned about the Fibonacci series and the various approaches to generate it along with their time and space complexities.

The different approaches we used are: Recursion, Dynamic Programming, While Loops, and Cache

Recommended Reading:

• Multithreading in Python
• Floor Division in Python
• Encapsulation in Python
• Switch Case in Python
• Literals in Python
• fibonacci series in c
   

To be more confident, you need to practice more competitive programming, and there are many questions to practice in data structures and algorithms to get into top product-based companies. You can check out Coding Ninjas studio, a platform where you can explore all the previous interview questions.