Memoization Fibonacci Algorithm In Python

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 ca

Solution 1:

It can be done with functools library in Python 3.2+

import functools

@functools.lru_cache(maxsize=None) #128 by defaultdeffib(num):
    if num < 2:
        return num
    else:
        return fib(num-1) + fib(num-2)

Solution 2:

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

deffastFib(n, memo):
    global numCalls
    numCalls += 1print'fib1 called with', n
    ifnot 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.

Solution 3:

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

from itertools import islice
deffibs():
    a, b = 0, 1whileTrue:
        yield a
        a, b = b, a + b

deffib(n):
    returnnext(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.

Solution 4:

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

classSolution:def__init__(self):
        # initialize memoself.memo = {}


    deffib(self, n: int) -> int:# base caseif n < 2:
            return n

        # check if fib(n) is already in memo - f(n) was calculated beforeif n inself.memo:returnself.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