CODEWITHSUNDEEP
javascriptrecursionfibonacci
thedoomer1000
thedoomer1000

Reputation: 73

Can't resolve memoization design pattern with fibonacci

I don't understand the last steps in the memoization design pattern. This is my code with classic fibonacci calculation:

//Memoization
      const fiboCache = () => {
        const cache = [0,1];
        const fibo = (x) => {
          let result = cache[x];
          if(typeof result !== 'number') {
            console.log('new calculation for: ' + x);
            result = fibo(x-1) + fibo(x-2);
            cache[x] = result;
          }
          return result;
        };
        return fibo;
      };
      const getFibo = fiboCache();
      console.log(getFibo(4));

The problem for me is the last step, I tried to break it down each iteration which looks like this:

4. result=undef; console.log; result=3; cache=[0,1,empty,empty,3]
3. result=undef; console.log; result=2; cache=[0,1,empty,2,3]
2. result=undef; console.log; result=1; cache=[0,1,1,2,3]
1. result=1; return 1;

I understand how the array is working as cache for my next calculations, but as soon as I'm on the last iteration (1) my result object becomes 1 which is breaking my recursion, and I'm going straight to return result.

Doesn't that mean I'm just returning 1 at the end? Shouldn't I return here the last item of my array?

Upvotes: 0

Views: 59

Answers (1)

Rup
Rup

Reputation: 34408

It's not quite that simple: you'll have to work up and down the recursion levels as each one returns. It'll go something like this

  • fibo(4), cache = [0,1] - not in cache; compute it from fibo(3) and fibo(2)
    • fibo(3), cache = [0,1] - not in cache; compute it from fibo(2) and fibo(1)
      • fibo(2), cache = [0,1] - not in cache; compute it from fibo(1) and fibo(0)
        • fibo(1), cache = [0,1] - return 1 from cache
        • fibo(0), cache = [0,1] - return 0 from cache
      • back to fibo(2): result = fibo(1) + fibo(0) = 1 + 0 = 1; write cache[2] = 1, return 1
      • fibo(1), cache = [0,1,1] - return 1 from cache
    • back to fibo(3): result = fibo(2) + fibo(1) = 1 + 1 = 2; write cache[3] = 2, return 2
    • fibo(2), cache = [0,1,1,2] - return 1 from cache
  • back to fibo(4), cache = [0,1,1,2]: result = fibo(3) + fibo(2) = 2 + 1 = 3; write cache[4] =3, return 3

i.e.

  • each recursion returns a value back to the level higher up, and you get the result from the top level = 3 not the first time you hit the return (1) as you'd thought
  • the cache is updated after each recursion level has completed; you'll never end up with [0,1,empty,empty,3] as you originally had.

It may also be instructive to step through this with a debugger and watch the cache contents and the call stack.

Upvotes: 1

Related Questions