Fibonacci Series In Python

Fibonacci Series In Python
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 Fn 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:

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: 

blog banner 1
  • 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

How do you print the Fibonacci series in Python?

A 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. This means the nth term is the sum of (n-1)th and (n-2)th term. The same pattern is followed for every programming language.

What is the Fibonacci series in Python using for-loop?

The Fibonacci series in python using for-loop is the same as while-loop. The code completely works fine. You need to convert the while condition to a for loop condition.

Is there a Fibonacci function in Python?

No, there is no Fibonacci function in python that is built-in. You can just add the function name into your class, and you can inherit it into your code if you want.

Is 0 a Fibonacci number?

The Fibonacci sequence is a series of numbers, where a number is the sum of the last two numbers, starting with 0 and 1. So 0 is one of the Fibonacci numbers.

What is the end in Python?

The end parameter is used to append any string at the end of the output of the print statement in python. By default, the print method ends with a newline.

Key Takeaways

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

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