8

I have this memoization technique to reduce the number of calls getting a Fibonacci sequence number: 

def fastFib(n, memo):
    global numCalls
    numCalls += 1
    print 'fib1 called with', n
    if not n in memo:
        memo[n] = fastFib(n-1, memo) + fastFib(n-2, memo)
        return memo[n]


def fib1(n):
    memo = {0:1, 1:1}
    return fastFib(n, memo)


numCalls = 0
n = 6
res = fib1(n)
print 'fib of', n,'=', res, 'numCalls = ', numCalls

But i am stuck at here: memo[n] = fastFib(n-1, memo) + fastFib(n-2, memo) and here memo = {0:1, 1:1}. How is it exactly reducing the number of calls each time i want to get fib of a number?

Improve this question
1
  • BTW - your memo should be: memo = {0:0, 1:1} and not memo = {0:1, 1:1} . Commented Sep 12, 2020 at 22:19

6 Answers 6

Reset to default
13

You should return memo[n] always, not only on unseccesful look up (last line of fastFib()):

def fastFib(n, memo):
    global numCalls
    numCalls += 1
    print 'fib1 called with', n
    if not n in memo:
        memo[n] = fastFib(n-1, memo) + fastFib(n-2, memo)
    #this should be outside of the if clause:
    return memo[n] #<<<<<< THIS

The number of calls is reduced this way, because for each value of n you actually compute and recurse from at most once, limitting the number of recursive calls to O(n) (upper bound of 2n invokations), instead of recomputing the same values over and over again, effectively making exponential number of recursive calls.

A small example for fib(5), where each line is a recursive invokation:

Naive approach:

f(5) = 
f(4) + f(3) = 
f(3) + f(2) + f(3) =
f(2) + f(1) + f(2) + f(3) =
f(1) + f(0) + f(1) + f(2) + f(3) = (base clauses) = 
1 + f(0) + f(1) + f(2) + f(3) = 
2 + f(1) + f(2) + f(3) =
3 + f(2) + f(3) = 
3 + f(1) + f(0) + f(3) = 
3 + 1 + f(0) + f(3) = 
5 + f(3) = 
5 + f(2) + f(1)  =
5 + f(1) + f(0) + f(1) =
5 + 1 + f(0) + f(1) =
5 + 2 + f(1) =
8

Now, if you use memoization, you don't need to recalculate a lot of things (like f(2), which was calculated 3 times) and you get:

f(5) = 
f(4) + f(3) = 
f(3) + f(2) + f(3) =
f(2) + f(1) + f(2) + f(3) =
f(1) + f(0) + f(1) + f(2) + f(3) = (base clauses) = 
1 + f(0) + f(1) + f(2) + f(3) = 
2 + f(1) + f(2) + f(3) =
3 + f(2) + f(3) =  {f(2) is already known}
3 + 2 + f(3) = {f(3) is already known}
5 + 3  = 
8

As you can see, the second is shorter than the first, and the bigger the number (n) becomes, the more significant this difference is.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Can you make a step by step explanation for the whole computation it does if you have enough time? Thanks
@MdSakib I just did, for f(5) example.
That's really great. I see how it reduces the redundant computation. Thank you
13

It can be done with functools library in Python 3.2+

import functools

@functools.lru_cache(maxsize=None) #128 by default
def fib(num):
    if num < 2:
        return num
    else:
        return fib(num-1) + fib(num-2)
Improve this answer

Comments

1

It can be done within a single class or a function as follows

class Solution:
    def __init__(self):
        # initialize memo
        self.memo = {}


    def fib(self, n: int) -> int:
        # base case
        if n < 2:
            return n

        # check if fib(n) is already in memo - f(n) was calculated before
        if n in self.memo:
            return self.memo[n]
        else:
            f = self.fib(n - 1) + self.fib(n - 2)

        # store the value of fib(n) when calculated 
        self.memo[n] = f 
   
        return f
Improve this answer

Comments

0

The following method uses a minimal cache size (2 entries) while also providing O(n) asymptotics:

from itertools import islice
def fibs():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

def fib(n):
    return next(islice(fibs(), n-1, None))

This implementation comes from the classic corecursive definition of fibonacci (a la Haskell's https://wiki.haskell.org/The_Fibonacci_sequence#Canonical_zipWith_implementation).

For a more direct (corecursive) translation see https://gist.github.com/3noch/7969f416d403ba3a54a788b113c204ce.

Improve this answer

Comments

0

Another solution without additional libraries or using a global variable:

def fib(n, memo):
    try:
        if memo[n]:
            # return memoized value
            return memo[n]
    except IndexError:
        pass

    if n == 1 or n == 2:
        # memoizing base cases
        result = 1
        memo.insert(0, 0)
        memo.insert(1, result)
        memo.insert(2, result)

    else:
        result = fib(n-1, memo) + fib(n-2, memo)
        memo.insert(n, result)

    return result

print(fib(8, []))
Improve this answer

Comments

0

I think the main idea being discussed here is how to use DP

Dynamic programming

to solve this problem

But I thought it would be nice to share this with you, This is based on quite hard mathematics, here is the link where you can find more info :Wikipedia

from math import sqrt

fib = lambda x : ((1+sqrt(5))/2)**n - ((1-sqrt(5))/2)**n

#Example 

print(fib(0), fib(1) , fib(2) , sep=" ," ) # returns 1 ,1 ,2

Or even easier use this But only for N bigger than 0 :

from math import sqrt 
fib2 = lambda x : round(((1+sqrt(5))/2)/sqrt(5),0)
print(fib2(1),fib2(2),fib2(3),sep=",") # returns 1,2,3
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.