DEV Community

loading...

Memoization in a Nutshell

pieohpah profile image Joe Chasinga Updated on ・4 min read

If anyone had ever set eyes on Cracking the Coding Interviews (or any other books on algorithms), you might at least know what memoization is and what it's good for. Consider this a more comprehensive, layman, JavaScript version of the excerpt.

There's no problem that can explain (bad) recursion simpler than finding the n fibonacci number, so here goes:


function fib(n) {
    if (n == 0 || n == 1) return n;
    return fib(n - 1) + fib(n - 2);
}

Enter fullscreen mode Exit fullscreen mode

Oh no, the syntax highlighting isn't working for you? No worries, that was just me. IMO, highlighting is quite distracting for reading code especially this small. It is helpful in writing, but you want to focus on the logical steps and make sure you get them while reading.

It's pretty straightforward. A recursive function with one or more base cases (in this case, when n == 0 and n == 1) and the recursive one. If you have no clue what how recursion works at all, I recommend a soft consultation of this post: Recursion Made Simple. (And don't forget to clap and follow me. It takes time and effort to write!)

The problem with the said fib function is it runs at exponential time O(2^n). That's like (almost) the worst runtime you could get into. How bad exactly? If you called fib(50) to compute the 50th fibonacci number and it took a minute to return the result, then calling fib(100) will take you roughly 1,125,899,906,000,000 minutes (rounded down to the millionth), which is just around 2 billion years (Fun fact: By then our earth and half of the solar system should have been eaten by the growing sun long ago).

To be fair, this problem is an intentional bad candidate for recursion. This recursive part:


fib(n - 1) + fib(n - 2);

Enter fullscreen mode Exit fullscreen mode

means that for every Nth node of the function call, two more branch out. To make this worse, for each Nth call, there are works repeated. Below is a painstakingly created ASCII tree diagram of what really happens:

                           fib(5)
                        /          \
                   fib(4)           fib(3)
                 /       \          /      \
             fib(3)   fib(2)       fib(2)  fib(1)
           /    \    /     \      /     \
          /      \ fib(1) fib(0) fib(1) fib(0)
       fib(2) fib(1)
      /      \
    fib(1) fib(0)


Enter fullscreen mode Exit fullscreen mode

As you can see, the work done from fib(3) down could be done once instead of repeated the way it is. When N = 5, you could see that fib(N - 2) is being computed twice, fib(N - 3) three times. If this goes on long enough, says N is a high number like 100, you can be sure that

For every fib(N), fib(N - (N - p)) will be repeated p times where p ∈ {x | 2 < x < N} (p is element of range (2..N-1)). Talking about baggages!

Memoization = Memorizing the past

As melodramatic as it may sound, that sums up the definition of this technique. Imagine your code is equipped with AI capability to not repeat the amount of work we mentioned. Still, the AI needs to have a way of memorizing what has been done. In this case, the fictitious AI isn't going to be of much help. The smartest thing it could do is to realize that the fib operation is a suicidal mission and switch to memoization mode from the get.

And what's the best way our brain remember and recall a memory quickly? By associating it with something else. That is exactly how associate arrays (hash map, hash table, dictionary) and arrays work!

In our fibonacci case, we could use either data structure, but array is simpler since the keys are already integers.

The concept is to have the fib function "carries along" an array filled with past memories so at any moment in its mesmerizing recursive life, it can recall that a work it's about to do had actually been done already and should just be lazy about it. Here is how it's done:


function fib(n, brain = []) {
    if (n == 0 || n == 1) return n;

    // If brain has no memory of the work for fib(n)
    if (brain[n] == 0) {

        // compute and then memorize it
        brain[n] = fib(n - 1, brain) + fib(n - 2, brain); 
    }

    // just returns what's already memorized
    return brain[n];
}

Enter fullscreen mode Exit fullscreen mode

Now whenever fib gets called, it carries along a brain with memories of the past work, just so that it could avoid doing work more than once. This will of course come with having to sacrifice a linear amount of space for brain array, but now you gets to finish computing fib(10000) in fractions of a millisecond instead of waiting for the universe to die out twice over.

p.s. I'll leave it to you to figure out the new runtime of our "mindful" fib.

ciaos

Discussion (11)

pic
Editor guide
Collapse
asaaki profile image
Christoph Grabo

One fix needed:

if (n == 0 || n == 1) n;

needs to be

if (n === 0 || n === 1) return n;

(also uses === as best practice)

Otherwise an error happens:

RangeError: Maximum call stack size exceeded
Collapse
pieohpah profile image
Joe Chasinga Author

Oh, shoot! Thank you. I thought that could implicitly return.

About the === it's very funny because now we don't have to use == again, although it is totally fine for integers like this case.

Collapse
asaaki profile image
Christoph Grabo

===: Yeah, I just picked up this habit, as it is usually the safer option, especially when processing external/user input.

return: JS is one of the langs without implicit returns. Nevertheless in the middle of a function we need to be explicit anyway, since more code follows afterwards. If implicit returns were supported you could use an else block to avoid a keyword, but also not worth the effort.

Thread Thread
pieohpah profile image
Joe Chasinga Author

Yeah I was hoping es6 is closer to functional than this. The only way to get an implicit return from the last expression is a lambda function without brackets (containing a single expression).

let fun = () => 0;
fun()           // will return 0
Collapse
asaaki profile image
Christoph Grabo

And for the brain version:

if (brain[n] === undefined) {

Or undefined will be the only result.

Collapse
thiht profile image
Thibaut Rousseau

The parallel with AI is really weird. Memoization is just a form of cache for pure functions, it's way simpler than anything AI related

Collapse
pieohpah profile image
Joe Chasinga Author

You're probably right. However, I was trying to kind of wrap this concept of memory / caching with the "brain". So I was trying to suggest that even with a super smart AI doing this it would still use this technique to memorize.

Collapse
itsjzt profile image
Saurabh Sharma

I understand recursion well enough, I just open the blog and clap for it

'cause It takes time and effort to write

Collapse
pieohpah profile image
Collapse
ben profile image
Ben Halpern

Nice overview Joe.

Collapse
pieohpah profile image