Fibonacci Function, Memoization

Today’s tech blog is about Fibonacci function. I have not had it in my tech interviews but as far as I understand it is a common question. If the time complexity on your fibonacci recursive solution is exponential, the technique to reduce the amount of time it takes to run this function is using memoization (it’s one of the ways to go about it).

The original solution is slow because of the duplicate calls with the same arguments to fibonacci function.

Memoization function stores arguments and results of each function call and returns precomputed results. We will retrieve the result from our space in the memory instead of running the function each time.

We will declare a function and pass another function fn as an argument in order to speed up our original function. We will declare cache — object that will store our arguments with its respective results. We are returning our function with the amount of arguments this function will be called with by using …args. We are going to look at the object and it’s keys and return cache[args] if it exists. If this function with these particular arguments was called before — return it with it’s results stored in cache object. Otherwise, we will call that function with the new arguments and cache the results inside of the cache object. Const result is set to call our original function fn and we use apply helper and store the result in the cache object. Finally we return the result.

function memoize(fn) {

const cache = {};

return function(…args) {

if (cache[args]) {

return cache[args];

}

const result = fn.apply(this, args);

cache[args] = result;

return result;

};

}

I learned about it from Stephen Grider who explained it so well. I suppose nothing is rocket science, only rocket science is. Happy Coding!