How to use "memoization" in fibonacci recursive function?

Question

The term "memoization" was introduced by Donald Michie in the year 1968. This is accomplished by memorizing the calculation results of processed input such as the results of function calls. If the same input or a function call with the same parameters is used, the previously stored results can be used again and unnecessary calculation are avoided.

My function:

def fibonnaci(n):

    if n ==0 or n == 1:
        return 1
    else:

        return fibonnaci(n - 1) + fibonnaci(n - 2), total_call


n =8
print(fibonnaci(n))

I did not understand how to use it in practice. Could anyone explain how to use memoization in fibonacci calculus?

Marat · Answer 1 · 2020-04-06T00:52:05.457

The easiest way is to use the built-in least-recently-used memoizer (note the fix in the return statement):

from functools import lru_cache                                                                     

@lru_cache()  # will cache 128 most recently used results by default. Use maxsize=.. to change this number
def fibonnaci(n): 
    if n ==0 or n == 1: 
        return 1 
    else:
        return fibonnaci(n - 1) + fibonnaci(n - 2)

Internally, the memoizer looks something like this:

def lru_cache(maxsize=128):
    cache = {}  # cache[key] = (count, return value)
    def wrapper(func):
        def _func(*args, **kwargs):
            cache_key = '::'.join(args)  # lazy version; don't try this at home
            if cache_key not in cache:
                # delete least recent used value
                key2delete = min(cache.keys(), key=lambda key: cache[key][0])
                del cache[key2delete]
                cache[cache_key] = [0, func(*args, **kwargs)]
            cache[cache_key][0] += 1
            return cache[cache_key][1]
        return _func
    return wrapper

without cache invalidation, it will simplify to:

def memoize(func):
    cache = {}  # cache[key] = value
    def wrapper(*args, **kwargs):
        cache_key = '::'.join(args)  # lazy version; don't try this at home
        if cache_key not in cache:
            cache[cache_key] = func(*args, **kwargs)
        return cache[cache_key]
    return wrapper

I reckon that you forgot -:> Internally, the memoizer looks something like this: — Laurinda Souza, Apr 06 '20 at 00:48
@LaurindaSouza added that part. This is more of a pseudocode, use with caution — Marat, Apr 06 '20 at 00:52
@Guimoute this is a simplistic way to construct cache key. Just slap all positional arguments into a single string, separating each argument with some fixed string, e.g. '::' — Marat, Apr 06 '20 at 01:23

How to use "memoization" in fibonacci recursive function?

1 Answers1