Memoization

 Basically in memoization we maintain a look up table where solutions are

stored so that we don’t have to solve the same sub problem again and again.

Instead we solve it once, and store the values so that they can be reused.

We know that Fibonacci sequence is:

F(n) = F(n-1)+F(n-2) if n>1

= n if n =0,1

So,

F(n):

if n<1:

return n

else :

return F(n-1)+F(n-2)

Here, we are making two recursive calls, and adding them up, and the value is returned.

Look at the following diagram:

Observe that just to find fibonacci(5), fibonacci(2) is computed three times and fibonacci(3) is computed two times. So, as n increases, fibonacci function’s(f(n)) performance goes down. The consumption of time and space would increase exponentially with increase in n. We can save time, by following a simple approach, that is to save a value when it is computed for the first time. So, we can save the values of F(1), F(2), F(3) and F(4) when they are computed for the first time, same way with F(3), F(4)…so on. So, we can say that:

F(n):

if n=<1:

return n

elif F(n) exist :

return F(n-1)

else:

F(n) = F(n-1)+F(n-2)

Save F(n)

Return F(n)

In the following code:

1. The function fibonacci() takes a number and creates a list, fib_num of size num+1. This is because the Fibonnaci series start from 0.

2. It calls the function fib_calculate(), which takes the number num and list fib_num as a parameter.

3. We have saved -1 at all index in the list:

a. If fib_num[num] is >0, that means Fibonacci for this number already exists, and we need not compute it again, and the number can be returned.

b. If num<= 1, then return num.

c. Else if num>=2, calculate fib_calculate(num - 1, fib_num) + fib_calculate(num - 2, fib_num). The value calculated must be stored in list fib_num at index num so that there is no need to calculate it again.

Code:

def fibonacci(num):

fib_num = [-1]*(num + 1)

return fib_calculate(num, fib_num)

def fib_calculate(num, fib_num):

if fib_num[num] >= 0:

return fib_num[num]

if (num<= 1):

fnum = num

return fnum

else:

fnum = fib_calculate(num - 1, fib_num) + fib_calculate(num - 2, fib_num)

fib_num[num] = fnum

return fnum

num = int(input('Enter the number: '))

print("Answer = ",fibonacci(num))

Execution:

num = int(input('Enter the number: '))

print("Answer = ",fibonacci(num))

Output:

Enter the number: 15

Answer = 610