Fibonacci Series in Python: Definition, Codes and More

Did you know that Python is the most widely used programming language in the world? Some of the biggest tech companies use it for a variety of their business applications. Python is a popular choice because it’s simple to use and read. It also comes with a lot of complementary tools considered appropriate for industry standards.

Python has a robust math module that is capable of carrying out a wide range of complex mathematical operations. In this blog, we will learn how to write a program to print the Fibonacci series in Python. Additionally, we will discover the 10 most useful and handy codes to find the nth number in Fibonacci Sequence.

What is the Fibonacci Series?

The Fibonacci sequence in Python is a collection of integers that begins with a zero. According to the rule, each number present in the Fibonacci series is equal to the sum of two consecutive numbers present before it. 

The first 14 numbers in the Fibonacci series are as follows.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233 

Starting with the third integer, each number follows the formula. For example, the first two numbers before the eighth number, 13, are 5 and 8. The sum of integers 5 and 8 adds up to 13. The Fibonacci series can go on forever till infinity if the formula is applied to each number.  

In mathematical terms, a Fibonacci series is defined using a recurrence relation. It is as follows:

Fn = Fn-1 + Fn-2

The seed values in this are:

F0 = 0 and F1 = 1

If you want to master this most popular programming language in the 21st century, consider pursuing a Python course.

Fibonacci Series Program in Python

In the program to print the Fibonacci series in Python, the method stores the number of terms specified by the user and initializes the first and second terms to 0 and 1 respectively.

Using a while loop, we can find the next term in the Fibonacci series by adding the previous two terms. This happens if there are more than two terms in the given series. Then we update it by switching the variables, and the process continues.

Below is the code to print the Fibonacci Series program in Python.

nterms = int(input("How many terms? "))

# first two terms
p1, p2 = 0, 1
count = 0

# check if the number of terms is valid
if nterms <= 0:
   print("Please specify a positive integer")
# if there is only one term, return p1
elif nterms == 1:
   print("Fibonacci sequence upto", nterms, ":")
   print(p1)

else:
   print("Fibonacci sequence:")
   while count < nterms:
       print(p1)
       nth = p1 + p2
       # update values
       p1 = p2
       p2 = nth
       count += 1

Also Read: Python String Functions With Examples

Fibonacci Series in Python: Print the nth Number

There are multiple methods to print the nth number in the Fibonacci series in Python. In this section, we will discuss some of them:

1. Python Code for Fibonacci Series Using Recursion 

Below is the function to print the nth Fibonacci number in Python using the Recursion method.

def Fibonacci(p):
    # Check if input is less than 0
    # then it will print incorrect input
    if p < 0:
        print("Input is incorrect")
    # Check if p is 0
    # then it will return 0
    elif p == 0:
        return 0
    # Check if p is 1 or 2
    # then it will return 1
    elif p == 1 or p == 2:
        return 1
    else:
        return Fibonacci(p - 1) + Fibonacci(p - 2)

# Driver Code
print(Fibonacci(11))


Output
89

The above program has:

• Time complexity: O(2 ^ n)  Exponential
• Auxiliary Space: O(n)

2. Fibonacci Series Code in Python Using Dynamic Programming

Below is the function to print the nth Fibonacci number in Python using Dynamic Programming. In this, we are taking the first two numbers in the Fibonacci sequence in Python as 0 and 1.

FibArray = [0, 1]

def fibonacci(p):
    # Check if p is less than 0
    if p < 0:
        print("Input is incorrect")
    # Check if p is less than len(FibArray)
    elif p < len(FibArray):
        return FibArray[p]
    else:
        FibArray.append(fibonacci(p - 1) + fibonacci(p - 2))
        return FibArray[p]

# Driver Program
print(fibonacci(12))


Output
144

The above program has:

• Time complexity: O(n)
• Auxiliary Space: O(n)

3. Fibonacci Series Using Space Optimization Approach

Below is the function to print the nth Fibonacci number in Python using Dynamic Programming with a space optimization approach.

def fibonacci(p):
    a = 0
    b = 1
    
    if p < 0:
        print("Input is incorrect")
        
    elif p == 0:
        return 0
    
    elif p == 1:
        return b
    
    else:
        for i in range(1, p):
            c = a + b
            a = b
            b = c
        return b

# Driver Program
print(fibonacci(14))


Output
377

The above program has:

• Time complexity: O(n)
• Auxiliary Space: O(1)

4. Fibonacci Series Code in Python Using Cache Technique

Below is the function to print the nth Fibonacci number in Python using a Cache technique.

from functools import lru_cache

@lru_cache(None)
def fibonacci(number: int) -> int:
    if number < 0:
        print("Input is incorrect")
        return
    elif number < 2:
        return number
    return fibonacci(number - 1) + fibonacci(number - 2)

# Driver Program
print(fibonacci(16))


Output
987

Also Read: OOPS Concepts in Python

5. Fibonacci Series Code in Python Using Backtrasing Approach

Let’s now see the function to print the nth Fibonacci number in Python using the Backtrasing approach.

def fibonacci(p, memo={}):
    if p <= 0:
        return 0
    elif p == 1:
        return 1
    elif p in memo:
        return memo[p]
    else:
        memo[p] = fibonacci(p-1) + fibonacci(p-2)
        return memo[p]

# Driver Program
print(fibonacci(18))


Output
2584

The below program has:

• Time complexity: O(n)
• Auxiliary Space: O(n)

6. Fibonacci Series Code in Python Using Backtrasing Approach

Here is the function to print the nth Fibonacci number in Python using the Backtrasing approach.

def fibonacci(p, memo={}):
    if p <= 0:
        return 0
    elif p == 1:
        return 1
    elif p in memo:
        return memo[p]
    else:
        memo[p] = fibonacci(p-1, memo) + fibonacci(p-2, memo)
        return memo[p]

# Driver Program
print(fibonacci(19))


Output
4181

The above program has:

• Time complexity: O(n)
• Auxiliary Space: O(n)

7. Fibonacci Series Code in Python Using Top-to-Bottom Approach

Mentioned below is the function to print the nth Fibonacci number in Python using the Top-to-Bottom approach.

dp = [-1 for i in range(10)]

def fib(p):
    if p <= 1:
        return p
    global dp
    
    first = 0
    second = 0

    if dp[p - 1] != -1:
        first = dp[p - 1]
    else:
        first = fib(p - 1)
        
    if dp[p - 2] != -1:
        second = dp[p - 2]
    else:
        second = fib(p - 2)
    
    dp[p] = first + second

    # Memoization
    return dp[p]

# Driver Code
if __name__ == '__main__':
    p = 7
    print(fib(p))


Output
13

The above program has:

• Time Complexity: O(n)
• Auxiliary Space: O(n)

8. Fibonacci Series Code in Python Using Binet’s Formula

Let’s take a look at the function to print the nth Fibonacci number in Python using Binet’s formula.

import math

def fibo(p):
    phi = (1 + math.sqrt(5)) / 2
    return round(pow(phi, p) / math.sqrt(5))
	
# Driver code
if __name__ == '__main__':
    p = 11
    print(fibo(p))


Output
89

The above program has:

• Time Complexity: O(logn) because calculating phi^n takes (log n) time
• Auxiliary Space: O(1)

9. Fibonacci Series Code in Python Using Power Matrix

We can now move on to the function to print the nth Fibonacci number in Python using a Power Matrix.

def fib(p):
    F = [[1, 1], [1, 0]]
    if p == 0:
        return 0
    power(F, p - 1)
    return F[0][0]

def multiply(F, M):
    x = F[0][0] * M[0][0] + F[0][1] * M[1][0]
    y = F[0][0] * M[0][1] + F[0][1] * M[1][1]
    z = F[1][0] * M[0][0] + F[1][1] * M[1][0]
    w = F[1][0] * M[0][1] + F[1][1] * M[1][1]
    F[0][0] = x
    F[0][1] = y
    F[1][0] = z
    F[1][1] = w

def power(F, p):
    M = [[1, 1], [1, 0]]
    for i in range(2, p + 1):
        multiply(F, M)

# Driver Code
if __name__ == "__main__":
    p = 18
    print(fib(p))

Output
2584

The above program has:

• Time Complexity: O(n)
• Auxiliary Space: O(1)

10. Fibonacci Series Code in Python Using Power Matrix and Time Optimization

This is the function to print the nth Fibonacci number in Python using a Power Matrix and Time Optimization.

def fib(p):
    F = [[1, 1], [1, 0]]
    if p == 0:
        return 0
    power(F, p - 1)
    return F[0][0]

def multiply(F, M):
    x = F[0][0] * M[0][0] + F[0][1] * M[1][0]
    y = F[0][0] * M[0][1] + F[0][1] * M[1][1]
    z = F[1][0] * M[0][0] + F[1][1] * M[1][0]
    w = F[1][0] * M[0][1] + F[1][1] * M[1][1]
    F[0][0] = x
    F[0][1] = y
    F[1][0] = z
    F[1][1] = w

def power(F, p):
    if p == 0 or p == 1:
        return
    M = [[1, 1], [1, 0]]
    power(F, p // 2)
    multiply(F, F)
    if p % 2 != 0:
        multiply(F, M)

# Driver Code
if __name__ == "__main__":
    p = 13
    print(fib(p))

Output
233

The above program has:

• Time Complexity: O(Logn) 
• Auxiliary Space: O(Logn)

Conclusion

This blog covered everything about the Fibonacci series in Python. We discovered how to write a Python program to print Fibonacci series as well as get the nth number of the Fibonacci series. So, now you know all the major ways to create this series using methods ranging from Recursion to Matrix and Backtrasing.