DEV Community

Cover image for Sequencing Fibonacci numbers
Tadea Simunovic
Tadea Simunovic

Posted on

Sequencing Fibonacci numbers

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
Enter fullscreen mode Exit fullscreen mode

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];
}
Enter fullscreen mode Exit fullscreen mode

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++) {
  }
}
Enter fullscreen mode Exit fullscreen mode

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];
  }
}
Enter fullscreen mode Exit fullscreen mode

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];
}
Enter fullscreen mode Exit fullscreen mode

Let's solve this problem using a recursive solution.

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

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;
}
Enter fullscreen mode Exit fullscreen mode

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.

Oldest comments (1)

Collapse
 
mayankjoshi profile image
mayank joshi

Amazing article. You have explained it both the way: naive approach & dynamic programming approach too.

I would love to see more such posts.