0

For a recursive implementation of a Javascript function to return the nth entry in the following recursive sequence 1,1,2,3,5,8,..., I have created a function that memoizes the result to cut down the execution time.

Here is the code:

//This is the memoization function.
function memoize(fn){
    const cache = {};
    return function(...args){
        console.log("Before: ",cache[args], Object.values(cache), 'Execution related to', ...args)
        if (cache[args]){

            return cache[args]
        } //If the key exists for the args, return its value.


        const result = fn.apply(null, args); //Call to the slowFib to get value.
        cache[args] = result;
        console.log("After function call to slowFib) ", cache[args], Object.values(cache), 'Execution related to', ...args)
        return result; //returns 1 for fib(1) and 0 for fib(0) base case.
    };
}

function slowFib(n){
    if(n<2){
        return n
    }
    return fib(n-1)+fib(n-2)
}

const fib = memoize(slowFib)

I understand how the recursive calls are being made and resolved, as well as how each of the inner functions is returned and invoked.

What I don't understand is how the cache object is updated.

I have investigated this by printing out values and executing the function to the console, and the following behavior in the picture confuses me:

enter image description here

Here, I have logged some variables over the course of the execution of fib(2) so that I can observe the behavior closest to the base case.

If you look at the expanded arrays, you will see that the cache object first stores the value 1 at the index of 0, for the execution of slowFib(1). However, when slowFib(0) is executed, we get a cache object that stores 0 at the 0th index and 1 at index 1.

I realize that the function somehow "remembers" that the value of 1 is supposed to be associated with 1, because it is called with slowFib(1), but it is stored in 0 because there is only one entry in the cache object.

Here are my questions:

  1. Since there are multiple cache objects created within the nested returns of memoize, how does Javascript interpret the assignments? Does the cache object closest to the base case somehow bubble up?

  2. How did the cache object retain the positional information to allow it to place 0 and 1 with the correct indexes as keys (if you look at the screenshot, you can see clearly how it placed 1 in at index 1 after placing it at index 0).

Thank you!

Richard K Yu
  • 2,152
  • 3
  • 8
  • 21
  • IMO this can be done with simple iteration instead of recursion, iteration is always faster and preferred way unless there's something which can't be solved by iteration – Code Maniac Aug 23 '19 at 01:44
  • Oooh the cache is only created once at the top! Got it. – Richard K Yu Aug 23 '19 at 01:54
  • But wait, aren’t I creating new instances when the inner function calls slowFib using apply, which leads to fib(n-1)+fib(n-2), which leads to memoize being called again with a new cache? – Richard K Yu Aug 23 '19 at 01:56
  • 1
    `memoize` is only called once, when you execute `fib = memoize(slowFib)` – Barmar Aug 23 '19 at 02:00
  • 1
    It creates a different instance of the closure each time it's called, but all the closures share the same binding of `cache`. – Barmar Aug 23 '19 at 02:01
  • @RichardKYu no, fib holds reference to return function of `memoize(slowFib)` so every time you call `fib` it calls that returned function not the `memoize` again – Code Maniac Aug 23 '19 at 02:02
  • @CodeManiac Ahh I see, so the assignment fib=memoize(slowFib) ensures that subsequent calls using fib refer back to the function that's still executing as a result of the assignment... – Richard K Yu Aug 23 '19 at 02:10

0 Answers0