Fibonacci Series In Python

Introduction

Are you looking for or dreaming of cracking jobs in top product-based companies like Amazon, Flipkart, Google, etc? Then you must know that competitive coding and data structures are quintessential topics to master, as they add a lot of value to your resume.

You need to practice data structures and algorithms problems every day to be good at them. One such important problem that is asked in many interviews is finding the Fibonacci series. This problem has many different approaches in different languages.

The article is completely written in python as it is one of the most popular and widely used languages.

 The Fibonacci series is a series in which each number is the sum of the preceding two numbers. By default, the first two numbers of a Fibonacci series are 0 and 1. 

In mathematical terms, the sequence F_n of Fibonacci numbers is defined by the recursive function.

Fn = Fn-1 + Fn-2

With seed values,

 F0 = 0 and F1 = 1.

We have many methods to find the Fibonacci series some are:

• Using While loop
• Recursion
• Dynamic Programming
• Space Optimised

Fibonacci Series using Recursion

The idea is to call the Fibonacci of n-1 and n-2 to get the nth Fibonacci number. The function would return 0 for 0, and 1 for 1.

Recurrence Relation = T(n) = T(n-1) + T(n-2).
Time complexity= O(2n)
Space complexity=O(n)

Recursive function works as: 

• If ‘n’ value is 0, the function returns 0.
• Else, if ‘n’ value is 1, the function returns 1.
• Else, call the recursive function for the value (n – 2) + (n – 1).

Code:

#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

Fibonacci series using Dynamic Programming

Another approach is to print the Fibonacci series using Dynamic programming. As the first two fixed values of the Fibonacci series are 0 and 1 and then we start our loop from the second index, in the loop we try to append the values using the previous two numbers.

Code:

#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:
Enter the value of ‘n’: 5
Output:
0 1 1 2 3

In the above program, first, we will check if n<0 so that the program prints Incorrect input. If n is greater than 0, we have two different options again. The basic idea is, to sum up, the n-1 and n-2 elements in the loop.

Time complexity= O(n)
Space complexity=O(n)

Fibonacci series using While Loops

To print the Fibonacci series we can use the while loop by using the basic conditions. By default, the first two numbers of a Fibonacci series are 0 and 1. The idea is to maintain the last two values of the series, and calculate the next element using these two values and update the last two values accordingly. 

Algorithm

• Input the ‘n’ value, the number of elements for which the Fibonacci series has to be generated.
• Initialise sum=0,a=0,b=1 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.

Code:

#Python program to generate Fibonacci series based on n value

n = int(input())
a = 0
b = 1
sum = 1
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: 0 1 1

When the input is taken, the process is done in a while loop. Here we swap a, b, and add them. Here a,b are pre-initialised in the program.

Time complexity= O(n)
Space complexity=O(1)

Frequently Asked Questions

Key Takeaways

This blog explained the methods to print the first ‘n’ elements using:

• Recursion
• Dynamic programming
• Loops

Practicing more problems on competitive coding can help you to stand out from the crowd during interviews. There are many questions to practice in data structures and algorithms to get into top product-based companies. 

This article discusses methods like recursion, dynamic programming, and space optimization. To solve more questions for interviews you can check out CodeStudio, a platform developed by experts, where you can find all previous interview questions.

Keep practicing, Keep hustling, The goal is near!

By Dharani Mandla