Returns the Nth value of a Fibonacci sequence.

_fibonacci.md

Fibonacci in JavaScript

These are possible examples of how to compute the Nth number of a Fibonacci sequence.

• fibFast uses a loop
• fibMemo uses memoization
• fibSlow uses recursion
• fibTail uses recrusion, with tail call optimization

Read more here…

https://en.wikipedia.org/wiki/Fibonacci_number

fibFast.js

/*
  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)
);

fibMemo.js

/*
  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)
);

fibSlow.js

/*
  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)
);

fibTail.js

/*
  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)
);