Exercise 13: Fibonacci Numbers

Directions

Print out the n-th entry in the fibonacci series. The fibonacci series is an ordering of numbers where each number is the sum of the preceeding two.

For example, the sequence

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

forms the first ten entries of the fibonacci series.

Example:

fib(4) === 3

Guidelines

Two solutions:

Iteractive

• the first two number cannot be used in a loop
• manually add the first 2 elements in array when declare
• loop index starts at 2
• Linear runtime

Recusive

• Classic example of recursion

• fib(5): 15 function calls; fib(6): 27 function calls
• Exponential runtime ($2^n$)! NOT acceptable
• How to improve the runtime?
  • Problem: fib() is being called multiple times with identical arguments
  • Solution: memoization Store the arguments of each function call along with the result. If the function is called again with the same arguments, return the precomputed result, rather than running the function again.
• Writing Memoization function
  • Note the runtime with memoization, much faster!

Solution

function fib(n) {
  let num = 0;
  let arr = [0, 1]; // manual add

  for (let i=2; i<=n; i++){ // start at 2
      num = arr[i-2] + arr[i-1];
      arr.push(num);    
  }

  return arr[n];
}

Alernative Solution: No Memoization

function fib(n){
  if (n <= 1){
    return n;
  }

  return fib(n-1) + fib(n-2);

}

Alernative Solution: with Memoization

function memoize(fn){
  const cache = {};

  return function(...args){
    if (cache[args]){ // had called
      return cache[args];
    }

    const result = fn.apply(this, args);
    cache[args] = result;
    return result;
  };
}

function slowFib(n){
  if (n <= 1){
    return n;
  }

  return fib(n-1) + fib(n-2); // make sure we call the right function
}

fib = memoize(slowFib);

// const fib = memoize(slowFib);

[Function]

fib(4)

3