Fibonacci, Recursion and Memorization in Python

Table of Contents

This is article not only how the fibonacci works, its related to how the recursion and memorization build in python.

First we going to see what is fibonacci series,

The list of fibonacci series is like 1,1,2,3,5,8,…. n. But some of us says the series like 0,1,1,2,3,5,8…n.

1st number = 1

2nd number = 1

3rd number = 1st +2nd = 1+1 = 2

4th number = 2nd+3rd = 1+2 = 3

same as like “n” th nnumber:

nth number = (n-2) + (n-1)

Normally we write fibonacci code is like below,

def fibo(n):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    elif n > 2:
        return (fibo(n-2) + fibo(n-1))
for n in range(1,6):
    print(n, ":", fibo(n))

Result:
1 : 1
2 : 1
3 : 2
4 : 3
5 : 5

But the same code not for all the values. May the value is a larger number like 100, 1000 we can't get output as like this.

Because it takes huge time to compute and give result.

RECURSION

Here the recursion function is used that’s why It’s getting too slow.

For example we are going to compute fibo(5)

This is what happens in this code, It’s unnecessary to recursive all the functions.

How we are going to solve this issue.

MEMORIZATION

We are going to do two important things in memorization,

Implement Explicitly
Use build-in python tool

In this Memorization we are not going to return the value directly.

we compute the value and cache it then return the value.

Code:

fibo_cache = {}               # Create a dictionary for cache
def fibo(n):
    #We are going to cache the value and return it
    if n in fibo_cache:
        return fibo_cache[n]
    #Compute the "n"th term
    if n == 1:
        value = 1
    elif n == 2:
        value = 1
    elif n > 2:
        value = fibo(n-1) + fibo(n-2)
    #Cache the value and return it
    fibo_cache[n] = value
    return value
for n in range(1,101):
    print(n, ":", fibo(n))