Fibonacci Series in Python | Algorithm, Codes, and more
Fibonacci Series in Python | Algorithm, Codes, and more
?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.?
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
?
Different Methods to print Fibonacci Series in Python are:
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(2n)
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:
Enter the value of 'n': 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 = 0
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
Time complexity?
The time complexity for this program is O(n)
Space complexity
The space complexity for this program is O(1)
You can practice by yourself with the help of online python compiler.
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 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 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.
The different approaches we used are below:
Important Links
??