Skip to content

Instantly share code, notes, and snippets.

@alanb1501
Last active August 29, 2015 14:03
Show Gist options
  • Save alanb1501/1f46a2b167ef5b8188b7 to your computer and use it in GitHub Desktop.
Save alanb1501/1f46a2b167ef5b8188b7 to your computer and use it in GitHub Desktop.
Fibonnaci
/*
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];
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment