Solving for the nth Fibonacci number
Tags: javascript, algorithms, career, showdev
Published: 2019-06-03 18:53:43

_Cover Photo Credit: Chloe Evans on Unsplash_

A classic interview question: “Please write a function `fibonacci` that takes an integer `n` and returns the nth Fibonacci number.” The Fibonacci sequence follows the following pattern:

```
0, 1, 1, 2, 3, 5, 8, 13…
```

The pattern continues by adding the previous two Fibonacci numbers together and therefore, the next value above would be `21`. Now let’s write a function to get the `n`th Fibonacci value so that,

```
// base Fibonacci numbers
fibonacci(0) // returns 0
fibonacci(1) // returns 1
// generated Fibonacci numbers
fibonacci(2) // returns 1
fibonacci(3) // returns 2
fibonacci(4) // returns 3
fibonacci(5) // returns 5
fibonacci(6) // returns 8
// ...
```

## Solution 1: Recursion

This is the most popular way of solving this problem because it is easier to reason about since,

```
fibonacci(n) = fibonacci(n - 1) + fibonacci(n - 2)
```

Let’s write this as a function:

```javascript
function fibonacci(n) {
  return fibonacci(n - 1) + fibonacci(n - 2)
}
```

This is great but, this has no stopping condition so it will go on forever. We need to specify that if `n` is `0` or `1` (our base Fibonacci numbers) we return `0` and `1`, respectively.

```javascript
function fibonacci(n) {
  if (n === 0) return 0
  else if (n === 1) return 1
  else return fibonacci(n - 1) + fibonacci(n - 2)
}
```

Great! Try the function out for `n = 1`, `n = 5`, and `n = 50`.

- `fibonacci(1)` should return `1`.
- `fibonacci(5)` should return `5`.
- `fibonacci(50)` should return `12586269025`.

You might have noticed that `fibonacci(50)` hangs in the console for some time. In fact, it took my console around eight minutes to execute!

![console showing an 8 minute execution of f(50)](https://thepracticaldev.s3.amazonaws.com/i/04yp9ugitae7cltf5xs0.png)

This is the downside to this solution. For large `n` , the computation time takes way too long. The second solution fixes this problem.

## Solution 2: Using a Generator Function

So the previous solution worked but, is super slow for large values of `n`.
Why is this the case? Well, let’s calculate `fibonacci(10)` as an example by hand (I will denote `fibonacci` as `f` for sake of simplicity.)

![long recursive tree for f(10)](https://thepracticaldev.s3.amazonaws.com/i/kem1ys3rhbl3ebs7dj9g.png)

We are having to dive into a bunch of the same rabbit holes over and over again to calculate `fibonacci(10)`. Why do we have to do this if all we need is the previous two Fibonacci numbers? Is there a way we can just _remember_ the previous two Fibonacci numbers and _generate_ the next Fibonacci number in the sequence? Yes! We can use [generators](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Generator) to create an infinite sequence of `Fibonacci` numbers. Generators are interesting. They are like regular functions but with super powers. They are able to return values without completely ending the execution of a function. It does this by making use of the special `yield` statement. Let’s look at a trivial example of a generator function.

```javascript
function* x() {
  // the "*" denotes that function x is a generator
  yield 'One taught me love'
  yield 'One taught me patience'
  yield 'And one taught me pain'
}
```

Great! Let’s invoke this function to see how it works:

```javascript
const thanku = x() // we invoke the generator

// invoke the `next` method on the generator prototype
thanku.next() // returns {value: "One taught me love", done: false}
thanku.next() // {value: "One taught me patience", done: false}
thanku.next() // {value: "And one taught me pain", done: false}
thanku.next() // {value: undefined, done: true}

// Now aren't you grateful for your x?
```

![Ariana Grande Wink - Thank u next.](https://i.giphy.com/media/1gUWdf8Z8HCxpM8cUR/giphy.webp)

For every call to the `next` method on the generator prototype, we get an object with two properties: `value` and `done` which is the value you are yielding from the generator and whether or not your generator is done generating values, respectively. Let’s look at a more interesting example. Let’s generate an infinite sequence of even numbers:

```javascript
function* even() {
  let start = 0
  yield start // yield 0 as our first even number
  while (true) {
    // the start of our infinite sequence!
    start += 2 // add 2 to start
    yield start
  }
}

function helper() {
  const value = evenNumbers.next()
  console.log(`NEXT: ${JSON.stringify(value)}`)
}

const evenNumbers = even()

setTimeout(helper, 1000)
setTimeout(helper, 2000)
```

Let’s go though the execution of the code above together:

1. We first Initialize the variable `evenNumbers` with the invocation of `even` generator.
2. We then wait `1000` milliseconds for the first invocation of `helper`.
3. `1000` milliseconds pass, and `helper` is invoked
   1. We initialize `value` with the invocation of `evenNumbers.next`
      1. We initialize `start` with `0`
      2. Then we `yield` `start` and _pause_ the generator.
   2. Now we `console.log` the `value`
4. Wait another `1000` milliseconds for the second invocation of `helper`
   1. We enter the `while` loop
      1. Increment `start` by 2.
      2. `yield` `start` and pause the generator.
   2. Now we `console.log` the `value`.

Great! So how do we use the generator function to get the nth Fibonacci number? What we want to do is

1. Create an infinite sequence of Fibonacci numbers using a generator.
2. Keep invoking `Fibonacci.next` until we get the nth Fibonacci number.

### 1. Create an infinite sequence of Fibonacci numbers using a generator

```javascript
function* Fibonacci() {
  let a = 0,
    b = 1 // base Fibonacci numbers
  while (true) {
    const c = a + b // next Fibonacci number
    yield c
    a = b // new a will be what used to be b
    b = c // new b will be what used to be c
  }
}
```

### 2. Keep invoking `Fibonacci.next` until we have the nth number

We can do this by using a standard `for` loop:

```javascript
function fibonacci(n) {
  if (n === 0) return 0
  else if (n === 1) return 1
  else {
    const Fib = Fibonacci()
    let value
    for (let i = 0; i < n - 1; i++) {
      value = Fib.next().value
    }
    return value
  }
}
```

And there you have it: a faster function to find the nth Fibonacci number. Look at the difference in speed! ~8 minutes vs ~0.029 milliseconds!

![console showing a 0.03 millisecond execution of f(50)](https://thepracticaldev.s3.amazonaws.com/i/8qs0see6qjy2uuezfpat.png)