生成斐波那契数列

function fib(n) {
  const arr = [0,1]; // the inital array, we need something to sum at the very beginning
  for (let i = 2; i <= n; i++) { // we want the last number, so don't forget the '=' sign
    let a = arr[i-1]; // previous Number
    let b = arr[i-2]; // the one before that
    arr.push(a+b); // push the result
  }
  return arr; // if you want the n-th number, just return arr[n] or arr.length - 1
}

console.log(fib(4));

// NOTE: This has extremly bad performance => Exponential time complexity 2^n

function fib(n) {
  if (n < 2) {
    return n;
  }
  return fib(n-1) + fib(n-2);
}

console.log('The n-th fibonacci number: ', fib(6));
console.log('The entire fibonacci sequence: ');

// Let's see the entire fibonacci sequence
for (let i = 0; i <= 6; i++) {
   console.log(fib(i));
}

// LET'S CREATE A MEMO FUNCTION 
// (and use it on the recursive **fib** function from above):

// We want to pass in a function which is going to, eventually, 
// use this utility function
function memo(fn) { 
  const cache = {}; 
  // let's make it reusable, and by that I mean, let's assume that
  // we don't know the number of arguments that will be eventually passed in 
 return function(...args) {
// if we already call this function with the same args?
// YES => return them
   if(cache[args]) { 
     console.log('cached', args[0]);
     return cache[args];
   }
//    otherwise, we want to call our function 
// (the one using this 'memo' function) and pass in the arguments
// w/ the help of 'apply'
   const res = fn.apply(this, args);
   cache[args] = res; 
   // we want to store the result, so later if we'll be able to
   // return that if the args don't change
   console.log('not cached', args[0]);
   return res; // don't forget to return the result of it :)
 }
}

// Now, let's use the memoized function:
// NOTE: Remember the above function has to change in a way
// that it calls the memoized function instead of itself

function fastFib(n) {
//   SAME LOGIC AS BEFORE
  if (n<2) { 
    return n;
  }
// But, here is where the 'magic' happens
// Very important: We want to call the instantiated 'fibMemo' function 
// and NOT 'fastFib', cause then it wouldn't be so fast, right :)   
  return fibMemo(n-1) + fibMemo(n-2);
}

// DO NOT CALL IT, JUST PASS IT IN
const fibMemo = memo(fastFib); 

// HERE WE WANT TO PASS IN THE ARGUMENT
console.log(fibMemo(6));

const fibonacci = (n, cache = {1: 1, 2: 1}) =>
  cache[n] || (cache[n] = fibonacci(--n, cache) + fibonacci(--n, cache));
  
console.log(fibonacci(1000));
console.log(fibonacci(100));
console.log(fibonacci(10));

var fibonacci = function(len) {
  var fib = function(seq) {
    var seqLen = seq.length;
    if (seqLen === len) {
      return seq;
    } else {
      var curr = seq[seqLen - 1];
      var prev = seq[seqLen - 2];
      seq[seqLen] = curr + prev;
      return fib(seq);
    }
  }
  return len < 2 ? [0] : fib([0, 1]);
}

console.log(fibonacci(100));

var sequence = [0,1];
var range = 10;

for(var i = 0; i < range-2; i++){
    sequence.push(sequence[i]+sequence[i+1]);
}

console.log(sequence);