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: Python Program for Fibonacci numbers 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 in Python
Python
# 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=' ')
You can also try this code with Online Python Compiler
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: Fibonacci Series Program 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 in Python
Python
# 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=' ')
You can also try this code with Online Python Compiler
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: Fibonacci Sequence 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 in Python
Python
# 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
You can also try this code with Online Python Compiler
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: Fibonacci Sequence Python Using 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 in Python
Python
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=' ')
You can also try this code with Online Python Compiler
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)
Applications of Fibonacci Series in Python
Applications of the Fibonacci series in Python include:
-
Mathematics: It's used in mathematical research, number theory, and the study of patterns and sequences.
-
Algorithms: Fibonacci numbers are the basis for various algorithms such as dynamic programming, memoization, and matrix exponentiation.
-
Optimization: Fibonacci sequences help optimize search algorithms, data structures, and time complexity in algorithms.
-
Financial Modeling: In finance, Fibonacci numbers are applied in modeling market trends, calculating investment strategies, and analyzing stock prices.
-
Graphics and Visualization: Fibonacci patterns are used in generating visually appealing designs, animations, and graphics.
-
Natural Sciences: Fibonacci sequences appear in nature, including the arrangement of leaves on a stem, the branching of trees, and the spirals of shells and flowers.
Also Read - Multilevel Inheritance in Python
Frequently Asked Questions
How do you add a Fibonacci series to a list in Python?
To add Fibonacci series to a list in Python, iterate through the desired range and append Fibonacci numbers to the list using a loop or list comprehension.
How do you write Fibonacci series in Python by recursion?
Write Fibonacci series in Python by recursion using a function that calls itself with the previous two Fibonacci numbers.
How do you solve Fibonacci for loop?
Solve Fibonacci using a for loop by iteratively updating variables to store the sum of the previous two Fibonacci numbers within the loop.
How to check whether a number is Fibonacci or not in Python?
To check if a number is a Fibonacci number in Python, calculate the square of 5 times the number squared plus or minus 4. If either result is a perfect square, the number is a Fibonacci number. This method is efficient and leverages unique properties of Fibonacci numbers.
Conclusion
In this article, we have discussed Python Program for Fibonacci numbers. We have discussed different approaches to finding the Nth Fibonacci sequence. We have also discussed its application in Python.
The different approaches we used are: Recursion, Dynamic Programming, While Loops, and Cache
Recommended Reading:
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.
84+ registered