CODEWITHSUNDEEP
javascriptrecursion
Mircea
Mircea

Reputation: 13

How does the cache update in javascript memoized fibonacci recursive function?

Considering the following recursive Fibonacci function that’s been optimized using memoization. No other code apart from this.

function memoizeFibonacci(index, cache = []) {
    if (cache[index]) {
        return cache[index]
    } else {
        if (index < 3) return 1
        else {
            cache[index] = memoizeFibonacci(index - 1, cache) + memoizeFibonacci(index - 2, cache)
        }
    }
    console.log(cache)
    return cache[index];
}
memoizeFibonacci(6)

Can someone please explain how is the cache array updated? When viewing the console logs the cache seems to hold all the previous values from the resolved recursive functions. But to me, this doesn't make sense as the cache is not stored outside memoizeFibonacci so the scope should not allow this.

Upvotes: 1

Views: 293

Answers (2)

jaume mila
jaume mila

Reputation: 31

Every nested recursive function adds its item when it resolves only during the chain of executions of the recursion.

console.log is asynchronous and probably shows repeatedly the final result. There is no specification about how console.log work so it can act differently depending on the environment, it's I/O.

Even if you make it work as expected in your environment, it can work differently for other user. An hypothesis based on the use of console in your algorithm is not correct.

Kyle Simpson references:

Upvotes: 1

ibrahim mahrir
ibrahim mahrir

Reputation: 31692

This has nothing to do with closures. This is simply passing the same array to nested recursive calls.

When you pass an array (or any object for that matter) to a function, the array is not copied, rather a reference to it is passed, so changing the array in the recursive call will affect the same array.

Here is an example of what is basically happening:

function foo(arr) {
  arr[0] = "hello";
}

let arr = [];
foo(arr);

console.log(arr); // changed because of the call to foo

Notice that the recursive calls to memoizeFibonacci is explicitly passing the cache object as the second parameter, so each recursive call is sharing the same array as the top-level call, and any changes to the cache object in the recursive calls is reflected in the top-level call aswell.

BTW, this type of memoization is not persistent, meaning that these two calls:

memoizeFibonacci(6);
memoizeFibonacci(10);

don't share the same cache object. They each use a different cache array that must be reconstructed from scratch rather than the call to memoizeFibonacci(10) using the cache object already constructed in the call to memoizeFibonacci(6) and appending to it. A more efficient memoization makes use of closures like in this example: https://stackoverflow.com/a/8548823/9867451

Note: If you are asking why all the console.log(cache) print out the same exact filled array, that's because they are printing the same array, and the values you see in the console are not necessarily added at the point of the console.log. Take a look at this other question: array.length is zero, but the array has elements in it. To log exactly what's in the cache object at the time of the console.log, change it to:

console.log(JSON.stringify(cache));

Upvotes: 0

Related Questions