js javascript interview fibonacci algorithms

- Introduction
- What is the Fibonacci sequence?
- Recursion
- While Loop
- For Loop
- For loop with an array
- Using Yield
- Performance

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.

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.

This is the shortest solution, but the slowest:

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

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:

```
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;
}
```

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]
}
```

```
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.

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

comments powered by Disqus