Algo Logging: The nth Fibonacci Number in JavaScript
Tags: algorithms, javascript, beginners, tutorial
Published: 2021-10-20 22:47:41

I vividly remember the first time I encountered the __nth Fibonacci__ algorithm. I had messaged a friend about starting to practice algorithms to which she responded:

> Yeah! I just did one on the Fibonacci Sequence today! So fun!

I was immediately filled with flashbacks of my Masters program, sitting in a 500-level Music Theory course, checking for the Fibonacci sequence and the Golden Ratio in Sonatas by Mozart and Schubert.

![David Rose from Schitt's Creek saying "That's a real quick no"](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/cb7s3fw2jf4em30a7kbq.gif)

Luckily for all of us, this algorithm problem's solution isn't as complicated as music theory at 8am. This time, it's the computer's job to figure out the sequence, we're just going to tell it how.

If you'd like to try the problem yourself first, you can find it here:

[CodeWars](https://www.codewars.com/kata/553e6558e848c5a3180000bc)
[LeetCode](https://leetcode.com/problems/fibonacci-number/)
___
## The Problem 

The __Fibonacci Number__ algorithm problem is as follows:
>*The Fibonacci sequence is derived of numbers where each number is the sum of the preceding numbers in the sequence. The sequence begins with 0 and 1.
Write a function that takes a integer, `n`, which represents an index in the sequence and return the Fibonacci Number held at that position.*

### Example

>*Fibonacci Sequence:* `0, 1, 1, 2, 3, 5, 8, 13...`
`n` *=* `4`
*output =* `3` 

___
## The Approach

We need a way to construct the Fibonacci sequence programmatically but we only need to construct it up to the `n`th position, and then return the number we find there.

It might be tempting to try this problem using recursion, where you call your function from within itself until you've reached the result:

```js
//a recursive solution

function nthFib(n) {
    if (n <= 1)
        return n;
    return nthFib(n-1) + nthFib(n-2);
}
```

However, this approach solves for the same number in the sequence multiple times, which problematic from an optimization standpoint, and that's the whole reason that you're here, is it not? 

You could clean this up a bit by using *memoization* (storing the results from a function call to prevent recalculating the same results again), but it's still going to run up space complexity (the amount of memory an algorithm takes up) with the memoization, which is wasteful, since we don't care about retaining the entire sequence in our output.

Instead, let's think about how *you* might solve this problem with your regular, human brain, not the computer. I'm thinking it would go like this:

  1. Start with `0` and `1`.
  2. Sum the next number in the sequence by adding your previous two numbers: `0 + 1 = 1`
  3. Sum the second-to-last of your previous numbers with your new number: `1 + 1 = 2`
  4. Repeat steps __2-3__ until you get to the `n`th position of the sequence.
  5. Tell me the answer you got.

Let's try that instead.

### Variables Used:

* `prevTwo` - an array that holds the previous two numbers of the sequence
* `i` - a counter variable in our `for` loop
* `sum` - the sum of `prevTwo[0]` and `prevTwo[1]` in the loop

### Line-by-Line Walkthrough:

```js
function nthFib(n) {...}
```

1. Initialize the variable `prevTwo` with a value of `[0,1]`, representing the start of the sequence {% collapsible show %}```js
  let prevTwo = [0, 1];
```{% endcollapsible %}

2. Create a `for` loop which will iterate until we've reached the `n`th number in the sequence, initialize variable `i` with value of `0`. {% collapsible show %}```js
for (let i = 0; i <= n; i++) {...
``` {% endcollapsible %} 


3. Inside of the loop, initialize a variable `sum` that is equal to `prevTwo[0]` + `prevTwo[1]`. {% collapsible show %}```js
  let sum = prevTwo[0] + prevTwo[1];
  ``` {% endcollapsible %} 

4. Still inside the loop, set the values held in `prevTwo` to be our *new* previous two numbers in the sequence, the number held at `prevTwo[1]` and our new `sum`. {% collapsible show %}```js
      prevTwo = [prevTwo[1], sum];
  }
 ``` {% endcollapsible %} 

5. When the loop is finished, return `prevTwo[1]`. This is our `n`th Fibonacci Number {% collapsible show %}```js
      return prevTwo[1]
  }
  ``` {% endcollapsible %} 

___
## Show Me The Logs

Here are my console.logs for this problem.

__For the best experience, view them on [replit](https://replit.com/@raquii/nth-fibonacci?v=1), where you can fork it and feed your own string into the function!__

```js
🚀 🚀 🚀 Nth FIBONACCI NUMBER STARTING NOW 🚀 🚀 🚀

                📥 n =  5

================= FOR LOOP: 1 OF 4 =================

    Fibonacci Sequence, so far: [ 0, 1 ] 

        🔸 prevTwo = [ 0, 1 ] 
        🔸 i = 0

        🧮 ...calculating sum... 🧮

            🔸 sum = 0 + 1 = 1

        → Moving 1 position [0]
        → Moving 1 into position [1]

        prevTwo is now [ 1 , 1 ]

================= FOR LOOP: 2 OF 4 =================

    Fibonacci Sequence, so far: [ 0, 1, 1 ] 

        🔸 prevTwo = [ 1, 1 ] 
        🔸 i = 1

        🧮 ...calculating sum... 🧮

            🔸 sum = 1 + 1 = 2

        → Moving 1 position [0]
        → Moving 2 into position [1]

        prevTwo is now [ 1 , 2 ]

================= FOR LOOP: 3 OF 4 =================

    Fibonacci Sequence, so far: [ 0, 1, 1, 2 ] 

        🔸 prevTwo = [ 1, 2 ] 
        🔸 i = 2

        🧮 ...calculating sum... 🧮

            🔸 sum = 1 + 2 = 3

        → Moving 2 position [0]
        → Moving 3 into position [1]

        prevTwo is now [ 2 , 3 ]

================= FOR LOOP: 4 OF 4 =================

    Fibonacci Sequence, so far: [ 0, 1, 1, 2, 3 ] 

        🔸 prevTwo = [ 2, 3 ] 
        🔸 i = 3

        🧮 ...calculating sum... 🧮

            🔸 sum = 2 + 3 = 5

        → Moving 3 position [0]
        → Moving 5 into position [1]

        prevTwo is now [ 3 , 5 ]

=============== 🏁 Finished Looping 🏁 ===============
  
        🌟 🌟 🌟 Final Solution 🌟 🌟 🌟

 The 5 th number in the Fibinacci Sequence is 5 ! 

```
___
## Solution

Finally, if you'd like to see a clean, log-free version of the solution, here it is:

{% spoiler View Solution %}
```js
function nthFib(n) {
  let prevTwo = [0, 1];

  for (let i = 0; i < n - 1; i++) {
    let sum = prevTwo[0] + prevTwo[1];
    prevTwo = [prevTwo[1], sum];
  }

  return prevTwo[1]
}
```
{% endspoiler %}

Thanks for reading and I wish you luck on whatever algorithmic endeavor brought you to this post. ♥