How to write Fibonacci sequence in Javascript


js javascript interview fibonacci algorithms

Hello! If you are from Ukraine, Belarus, Poland or India and looking for a job in Software Development, please reach me out by email.

Table of contents

Introduction

In this post, we will check how to write Fibonacci sequence in Javascript with:

  • recursion
  • while loop
  • for loop
  • for loop with an array

And we will check the performance.

What is the Fibonacci sequence?

Fibonacci sequence is a series of numbers, where a number is the sum of the last two numbers. The first 2 numbers either 1 and 1 or 0 and 1.

Recursion

This is the shortest solution, but the slowest:

const fib = n => {
  if (n <= 1) { return n; } 
  return fib(n - 1) + fib(n - 2);
}

While Loop

This is the one of the fastest solutions along with loop:

const fib = n => {
  let [a, b, temp] = [1, 0];
  
  while(n >= 1){
    temp = a;
    a = a + b;
    b = temp;
    n--;
  }
  return b;
}

The loop is the fastest solution for calculating the Fibonacci sequence:

For Loop

const fib = n => {
  let [prev, next] =  [0, 1];

 for (let i = 0; i < n; i++) {
   let temp = next;
   next = prev + next;
   prev = temp;
  }

 return prev;
}

For loop with an array

We are creating an array and return the latest item of this array:

const fib = (n) => {
	const arr = []

	arr[0] = 0
	arr[1] = 1
	for (let i = 2; i <= n; i++) {
		arr[i] = arr[i - 2] + arr[i - 1]
	}
	return arr[arr.length - 1]
}

Yield

function *fibonacci(n, current = 0, next = 1) {
  if (n === 0) { return current; }
  yield current;
  yield *fibonacci(n-1, next, current + next);
}

console.log([...fibonacci(10)])

Important: Please don’t use generators for recursion purpose. It could be the reason of maximum call stack size exceeded.

Performance

I have combined all functions and tested them on https://jsbench.me/. Here is a result:

JSBench.me results

comments powered by Disqus