Sequencing Fibonacci numbers

#javascript #challenge #code #algorithms

By definition, the first two numbers in the Fibonacci sequence are either 1 and 1, or 0 and 1, depending on the chosen starting point of the sequence, and each subsequent number is the sum of the previous two.

The Fibonacci series is an ordering of numbers where
each number is the sum of the preceding two.

Here is an example of the Fibonacci Sequence

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ….

Challenge

Print out the n-th entry in the Fibonacci series.
For example, the sequence [0, 1, 1, 2, 3, 5, 8, 13, 21, 34] forms the first ten entries of the Fibonacci series.
Example:
fib(4) === 3

How Fibonacci works is to look at two previous numbers and add them together. Since we know we are starting with zero and one, the best way would be to just manually insert 0 and 1 into the result set.

function fibonacci(n) {
  const result = [0,1];
}

Now we will use a for loop to start from a number that is on [2] and iterate all the way to the n number.

function fibonacci(n) {
  const result = [0,1];
 for (let i = 2; i <= n; i++) {
  }
}

In the for loop, we will need to pull previous two number that is in const result and we will add them together and push back to const result.

function fibonacci(n) {
  const result = [0,1];
 for (let i = 2; i <= n; i++) {
   const a = result[i - 1];
   const b = result[i - 2];
  }
}

We will add these two numbers together and push it to const result and return entry (n) from result.

function fibonacci(n) {
  const result = [0,1];
 for (let i = 2; i <= n; i++) {
   const a = result[i - 1];
   const b = result[i - 2];

   result.push(a + b);
  }
  return result[n];
}

Let's solve this problem using a recursive solution.

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

This would be exponential runtime, the fibonnaci function is being called multiple times with the same exact arguments.

To improve the runtime, we can use memoization.
Memoization - store the arguments of each function call along with the result. If the function is called again with the same arguments, return the precomputed result, rather than running the function again.

var cache = {};

function fibonacci(number) {

    if (number < 1)
        return 0;

    if (number <= 2)
        return 1;

    if (number in cache)
        return cache[number];

    var value = fibonacci(number- 1) + fibonacci(number - 2);

    cache[number] = value;

    return value;
}

Using a variable var cache will remember function execution result and if the arguments for the future function execution are already in the cache we will simply return this value.

Memoization will assure us that for each number Fibonacci function will only be executed once.