0
\$\begingroup\$

Trying to applying what seen on What Is Dynamic Programming and How To Use It (here: https://www.youtube.com/watch?v=vYquumk4nWw ) Obviuously this is the final code, after removing the recursion. I thought it was a good idea to memoize just the latest two values instead of the whole sequence. I could replace the array with two values and a temp one to make the shift but maybe it will affect readability. What you think ?

fibonacci: function (n)
{
    if (n === 0 || n === 1) return 1;

    var array = [1, 1];

    for (var i = 2; i < n; i++) {
        array.push(array[0] + array[1]);
        array.shift();
    }

    return array[0] + array[1];
}
\$\endgroup\$
2
\$\begingroup\$

Your code will accomplish the task of returning the Nth Fibonacci number and will do it quite fast. But you are not getting the point of the video, how to do Memoization.

To improve your code:

  1. Defining your variables at the beginning of your function.

  2. Indent your if block and surround with { }

    fibonacci: function (n)  {
      var array = [1, 1]; // prevent variable  hoisting 
      var i = 2;          // defining var at start of function        
      if (n === 0 || n === 1) {
        return 1;  // indent if block and surround with {}
      }
      for (; i < n; i++) {
        array.push(array[0] + array[1]);
        array.shift();
      }
    
      return array[0] + array[1];
    }
    

Memoization is more efficient by storing or memorizing past results to get faster future results the NEXT time you call the function. If you call fibonacci(701) then fibonacci(700), you will calculate the results both times. If you memoize the function you will look up the result on the second call. If you call fibonacci(702) you will look up the last two values to get the next result.

You have NO memoized values.

function fibonacci (n, pastResults)
{
  var memo = pastResults || [1, 1]; //if no pastResults, set default value
  var i = memo.length;
  if (i > n) { // we have result 
    console.log('looking up value')
    return {  //return 2 values
        pastResults: memo,
        result: memo[n-1]
    };  // return it
  }
  for (; i < n; i++) {
    memo[i] = memo[i-1] + memo[i-2];
  }

  return {
    pastResults: memo,
    result: memo[n-1]
  };
}

var r = fibonacci(7)
console.log(r.result) //13
r = fibonacci(5, r.pastResults);  // looking up value
console.log(r.result) //5
console.log(r.pastResults) //[1, 1, 2, 3, 5, 8, 13], these will not be recalcuated
r = fibonacci(22, r.pastResults);  
console.log(r.result) //17711

Here is a more eloquent, but harder to understand solution.

Note, in my 13+ years of JavaScript development, I've never used Memoization in production code.

References:

...coming soon

...Bock scope vs Function scope reference soon

https://github.com/dwyl/Javascript-the-Good-Parts-notes#memoization

\$\endgroup\$
  • \$\begingroup\$ Oh, shame on me. It was my first try with Memoization and i complete misunderstood it Thanks a lot, I'm working hard on studying your github guide :) \$\endgroup\$ – TheQult Sep 19 '18 at 12:34
  • \$\begingroup\$ That's OK. That is why I love code reviews. \$\endgroup\$ – Mke Spa Guy Sep 20 '18 at 0:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.