Memoization Benefits

index.html

<div class="container">
  <h1>Fibonacci Sequence</h1>
  <form>
    <div class="form-group">
      <label for="number">
        Fibonacci sequence number:
      </label>
      <input type="number" class="form-control" name="number" id="number" min="1" value="1" />
      <small class="form-text text-muted">Please enter a number in the fibonacci sequence where n > 0.</small>
    </div>
  </form>
  <hr />
  <h2>Calculate using the following methods</h2>
  <div class="btn-group" role="group" aria-label="Basic example">
    <button class="btn btn-primary" id="calculate-for" >For loop</button>
    <button class="btn btn-danger" id="calculate-recursive">Recursive</button>
    <button class="btn btn-primary" id="calculate-recursive-memoized">Recursive, memoized</button>
  </div>

  <button class="btn btn-default" id="clear-results">Clear Results</button>
  <hr />
  <h3>Results:</h3>
  <div id="results"></div>
</div>

memoization-benefits.markdown

Memoization Benefits

Shows the reasons you might want to memoize a function like the fibonacci sequence.

A Pen by Connor MacDonald on CodePen.

License.

script.babel

class fibonacciApp {
  constructor() {
    this.tolerableTimeThreshold = '100';
    this.elements = {
      results: document.getElementById('results'),
      number: document.getElementById('number'),
      buttons: {
        for: document.getElementById('calculate-for'),
        recursive: document.getElementById('calculate-recursive'),
        recursiveMemoized: document.getElementById('calculate-recursive-memoized'),
        clear: document.getElementById('clear-results')
      }
    };
    /**
     * TODO: LOL figure out a better way to memoize this
     */
    this.fibonacciRecursiveMemoized = (function() {
      var memo = {};
      function fib(n) {
        var value;
        if (n === 0 || n === 1) {
          value = n;
        } else {
          if (n in memo) {
            value = memo[n];
          } else {
            value = fib(n-1) + fib(n-2);
            memo[n] = value;
          }
        }
        return value;
      }
      return fib;
    })();
    
    this.registerEventListeners();
  }
  registerEventListeners() {
    this.elements.buttons.clear.addEventListener('click', () => {
      this.elements.results.innerHTML = ' ';
    })
    this.elements.buttons.recursiveMemoized.addEventListener('click', () => this.executeAlgorithm(this.fibonacciRecursiveMemoized));
    // TODO: Could we not bind this? Makes printing out the funnction a little more difficult.
    this.elements.buttons.recursive.addEventListener('click', () => this.executeAlgorithm(this.fibonacciRecursive.bind(this))); 
    this.elements.buttons.for.addEventListener('click', () => this.executeAlgorithm(this.fibonacciFor));
  }
  
  executeAlgorithm(method) {
    let value = this.elements.number.value;
    try {
      let valueInteger = parseInt(value);
      if (valueInteger >= 0) {
        let startTime = new Date().getTime();
        let result = method(valueInteger); 
        let endTime = new Date().getTime();
        this.printResults(
          value,
          result,
          endTime - startTime,
          method
        )  
      } else {
        throw { message: `Invalid integer ${value}` };
      }
      
    } catch (e) {
      this.printException(e.message, value, method);
    }
  }
  
  printResults(n, result, executionTime, method) {
    this.elements.results.innerHTML +=
    `<div class="alert ${(executionTime>this.tolerableTimeThreshold) ? 'alert-warning' : 'alert-secondary'}">
  <ul class="list-group">
    <li class="list-group-item active"><strong>Result:</strong> ${result}</li>
    <li class="list-group-item"><strong>Method:</strong> ${method.name}</li>
    <li class="list-group-item"><strong>Input for parameter n:</strong> ${n}<br></li>
    <li class="list-group-item"><strong>Execution Time:</strong> ${executionTime} ms <br></li>
  </ul>
  <hr>
  <h3>What just ran:</h3>
  <pre>${method.toString()}</pre>
  </div>`;
  }
  /**
   * Add an exception to the list of things printed to the screen
   */
  printException(errorText, n, method) {
    this.elements.results.innerHTML +=
    `<div class="alert alert-danger">
    <strong>Method:</strong> ${method.name} <strong>n:</strong> ${n}
    <pre>EXCEPTION<br />${errorText}</pre>
    </div>`;
  }
  
  /*
   * Run the fibonacci sequence in a recursive pattern to achieve the result.
   * This has a big performance hit after about 32.
   * the complexity of this algorithm is about 2^n
   */
  fibonacciRecursive(n) {
    if (n === 0 || n === 1) {
      return n; 
    }
    else {
      return this.fibonacciRecursive(n - 1) + this.fibonacciRecursive(n - 2); 
    }
  }
  
  /**
   * Fibonnaci sequence completed going in the normal algorithm.
   * Although less "elegant", this is significantly less complex.
   */
  fibonacciFor(n) {
    let accumulator = 1,
        previousNMinus1 = 0,
        previousNMinus2 = 1;
    for (var counter = 1; counter <= n; counter++ ) {
        accumulator = previousNMinus1 + previousNMinus2;
        previousNMinus2 = previousNMinus1;
        previousNMinus1 = accumulator;
    }
    return accumulator;
  }
  
  
}

let fib = new fibonacciApp();

styles

<link href="https://cdnjs.cloudflare.com/ajax/libs/twitter-bootstrap/4.0.0-beta/css/bootstrap.min.css" rel="stylesheet" />