Fibonacci Series in Python

In this article, we are going to write program for the Fibonacci Series in Python. Additionally, we will also create a program that tells whether a number is a Fibonacci number or not.

Table Of Contents

1. Introduction to fibonacci series
2. Fibonacci series using for loop
3. Fibonacci series using recursion
4. Fibonacci series using memoization
5. Identify Whether A Number Is Fibonacci Or Not
6. Conclusion

Introduction To Fibonacci series

A Fibonacci series is a series of numbers in which each number is the sum of the last two numbers in the series. The first two numbers in the series are 0 and 1.

The series was named after the Italian mathematician Leonardo Pisano Fibonacci, who introduced it in 1202 in his book.

The series looks like this: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, …

Starting from 0 and 1, the next number is (0 + 1) = 1, and the next number is (1 + 1) = 2, and so on.

Fibonacci series using for loop

Let's see how we can generate the Fibonacci series using for loop.

Algorithm

1. Initialize prev and curr to 0 and 1 respectively. These are the first two numbers in the series.
2. Create a for loop to iterate through the range of 0 to n.
3. For each number in the series, calculate the next number by adding the previous two numbers in the series.
4. Swap the number. Make the current number the previous number and the newly generated number the current number.
5. Return the previous number.
6. Later you can print the series.

# Fibonacci series using for loop
def fibonacci(n):
    prev, curr = 0, 1

    # calculate nth Fibonacci number
    for i in range(n):
        num = curr
        curr = prev + curr
        prev = num
    return prev
    
# print the Fibonacci series
for i in range(10):
    print(f"{i}th Fibonacci number is {fibonacci(i)}")

Output:

0th Fibonacci number is 0
1th Fibonacci number is 1
2th Fibonacci number is 1
3th Fibonacci number is 2
4th Fibonacci number is 3
5th Fibonacci number is 5
6th Fibonacci number is 8
7th Fibonacci number is 13
8th Fibonacci number is 21
9th Fibonacci number is 34

Fibonacci Series in Python using recursion

The recursion is a technique to solve a problem by calling a function within itself. The function calls itself until the base case is reached.

Here the base case is when the number is 0 or 1.

Let's first see the Python program to generate the Fibonacci series using recursion then we will look at its working.

# fibonacci series using recursion
def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

# call function
for i in range(5, 13):
    print(f"{i}th Fibonacci number is {fibonacci(i)}")

Output:

5th Fibonacci number is 5
6th Fibonacci number is 8
7th Fibonacci number is 13
8th Fibonacci number is 21
9th Fibonacci number is 34
10th Fibonacci number is 55
11th Fibonacci number is 89
12th Fibonacci number is 144

Here is how the function works:

If the number is 0 or 1, then the number is returned (which is the base case). When the number is greater than 1, the function calls itself again. For example, if number is 2 then else part of the function is executed and return fibonacci(2 - 1) + fibonacci(2 - 2), which is 1 + 0 = 1.

Similarly, if number is 3 then else part of the function is executed and return fibonacci(3 - 1) + fibonacci(3 - 2), which is fibonacci(2) + fibonacci(1), which is 1 + 1 = 2, and so on.

Fibonacci Series in Python using memoization

The recursive function discussed above is terribly slow for large numbers. The reason is that because of recursion the function has to calculate the Fibonacci value of the same number multiple times at the different stages of the function execution. Which is a very expensive operation.

You can see in the above figure, that to calculate the 5th Fibonacci number f(5), the execution calculates f(2) 3 times, f(3) 2 times, and f(4) for 1 time. You can imagine how complex the calculation gets as soon as the number gets bigger.

We can solve this problem if we store the calculated value of f(n). So that we don't have to calculate the same value again.

Here comes the memoization. It is a technique to store the result of a function call and use it later.

The value store is in a dictionary. The key is the number and the value is the Fibonacci value.

# fibonacci series using memoization
def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    else:
        memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
        return memo[n]

# call function
for i in range(50, 55):
    print(f"{i}th Fibonacci number is {fibonacci(i)}")

Output:

50th Fibonacci number is 12586269025
51th Fibonacci number is 20365011074
52th Fibonacci number is 32951280099
53th Fibonacci number is 53316291173
54th Fibonacci number is 86267571272

You can also calculate the Fibonacci number using this for larger values. For example, the 100th Fibonacci number is 354224848179261915075.

Identify the Fibonacci number

According to Binet's formula, a number N is a Fibonacci number if and only if one or both of 5 × N × N + 4 or 5 × N × N + 4 is a perfect square. (source: Wikipedia)

We can use the above formula to identify the Fibonacci number.

# identify the Fibonacci number
from math import sqrt

def is_fibonacci(n):
    return sqrt(5 * n * n + 4) % 1 == 0 or sqrt(5 * n * n - 4) % 1 == 0

# check if the number is Fibonacci
for i in range(1, 100):
    if is_fibonacci(i):
        print(f"{i} is a Fibonacci number")

Output:

1 is a Fibonacci number
2 is a Fibonacci number
3 is a Fibonacci number
5 is a Fibonacci number
8 is a Fibonacci number
13 is a Fibonacci number
21 is a Fibonacci number
34 is a Fibonacci number
55 is a Fibonacci number
89 is a Fibonacci number