These are possible examples of how to compute the Nth number of a Fibonacci sequence.
fibFast
uses a loopfibMemo
uses memoizationfibSlow
uses recursionfibTail
uses recrusion, with tail call optimization
Read more here…
These are possible examples of how to compute the Nth number of a Fibonacci sequence.
fibFast
uses a loopfibMemo
uses memoizationfibSlow
uses recursionfibTail
uses recrusion, with tail call optimizationRead more here…
/* | |
This method loops with incremental | |
"cache" variables, and finds the | |
Nth value of a Fibonnaci sequence. | |
This method is faster, because | |
it does not need recursion. | |
*/ | |
const fibFast = (value = 1) => { | |
// Early exit. | |
if (value <= 2) { | |
return 1; | |
} | |
// Set later. | |
let itemOne = 1; | |
let itemTwo = 1; | |
// Loop until value. | |
for (let i = 3; i <= value; i++) { | |
// Compute subtotal. | |
const subtotal = itemOne + itemTwo; | |
// Move item "two" into item "one." | |
itemOne = itemTwo; | |
// Move subtotal into item "two". | |
itemTwo = subtotal; | |
} | |
// Expose number. | |
return itemTwo; | |
}; | |
/* | |
Example usage. | |
NOTE: This can easily handle a | |
larger number than `fibSlow`. | |
*/ | |
console.log( | |
// Logs `354224848179262000000`. | |
fibFast(100) | |
); |
/* | |
This method loops with incremental | |
"cache" memoization, and finds the | |
Nth value in a Fibonnaci sequence. | |
This method is fast, but incurs a | |
memory overhead by caching values. | |
*/ | |
const fibMemo = (value = 1) => { | |
// Early exit. | |
if (value <= 2) { | |
return 1; | |
} | |
// Set in loop. | |
const cache = [0, 1, 1]; | |
// Loop through. | |
for (let i = 3; i <= value; i++) { | |
// Get subtotal. | |
const subtotal = cache[i - 1] + cache[i - 2] | |
// Add to cache. | |
cache[i] = subtotal; | |
} | |
// Expose last item. | |
return cache[cache.length - 1]; | |
}; | |
/* | |
Example usage. | |
NOTE: This can easily handle a | |
larger number than `fibSlow`. | |
But it consumes more | |
memory than `fibFast`. | |
*/ | |
console.log( | |
// Logs `354224848179262000000`. | |
fibMemo(100) | |
); |
/* | |
This method loops recursively | |
and returns the Nth value of | |
a Fibonacci number sequence. | |
It is inherently slow. | |
*/ | |
const fibSlow = (value = 1) => { | |
// Early exit. | |
if (value <= 2) { | |
return 1; | |
} | |
// Everything else. | |
return fibSlow(value - 1) + fibSlow(value - 2); | |
}; | |
/* | |
Example usage. | |
NOTE: Do not specify too high of | |
a number, or your browser tab may | |
freeze due to looping recursion. | |
*/ | |
console.log( | |
// Logs `610`. | |
fibSlow(15) | |
); |
/* | |
This method loops recursively | |
and returns the Nth value of | |
a Fibonacci number sequence. | |
It uses tail call optimization, | |
so it does not suffer from the | |
same sluggishness of `fibSlow`. | |
*/ | |
const fibTail = (value = 1, itemOne = 1, itemTwo = 1) => { | |
// Early exit. | |
if (value <= 2) { | |
return itemOne; | |
} | |
// Shift items. | |
const newValue = value - 1; | |
const newItemOne = itemOne + itemTwo; | |
const newItemTwo = itemOne; | |
// Recursion. | |
return fibTail(newValue, newItemOne, newItemTwo); | |
}; | |
/* | |
Example usage. | |
NOTE: This can easily handle a | |
larger number than `fibSlow`. | |
*/ | |
console.log( | |
// Logs `354224848179262000000`. | |
fibTail(100) | |
); |