Fibonnaci

fib.js

/*
A fibonacci number is defined as the sum of the previous 2 numbers in the sequence. 
By definition, the first 2 fibonacci numbers are 1 and 1. 
Thus the sequence goes: 1,1,2,3,5,8,13,21,34...n-2,n-1,n
or more plainly put:

Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2)

Below are 4 different solutions to calculate the Nth number in the fibonacci sequence
*/

// Basic recursive
fib(n) {

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


//basic recursion with memoization
var cache={};
fib2(n) {
  if(n < 2) { 
    return 1;
  }
  
  if(cache[n]) {
    return cache[n];
  }
  else {
   var ret = fib2(n-1) + fib2(n-2);
   cache[n] = ret;
   return ret;  
  }
}

//iterative solution
fib3(n) {
 var fib, n1 = 1, n2 = 1;
 if(n < 2) {
    return 1;
 }

 for(var i = 2; i < n; ++i) {
   fib = n1 + n2;
   n2 = n1;
   n1 = fib;
 }
 
 return fib;
}
  
//iterative inplace solution
fib4(n) {
   var ar = [1,1];
   for(var i = 0; i < n; ++i) {
      ar[i % 2] = ar[i % 2] + ar[(i+1) % 2];
   }
   return ar[n % 2];

}