## DEV Community 👩‍💻👨‍💻 # Algo Logging: The nth Fibonacci Number in JavaScript

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

## 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:

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

### 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` and `prevTwo` in the loop

### Line-by-Line Walkthrough:

``````function nthFib(n) {...}
``````
1. Initialize the variable `prevTwo` with a value of `[0,1]`, representing the start of the sequence

show
``````let prevTwo = [0, 1];
``````

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

show
``````for (let i = 0; i <= n; i++) {...
``````

3. Inside of the loop, initialize a variable `sum` that is equal to `prevTwo` + `prevTwo`.

show
``````let sum = prevTwo + prevTwo;
``````

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` and our new `sum`.

show
``````  prevTwo = [prevTwo, sum];
}
``````

5. When the loop is finished, return `prevTwo`. This is our `n`th Fibonacci Number

show
``````  return prevTwo
}
``````

## Show Me The Logs

Here are my console.logs for this problem.

For the best experience, view them on replit, where you can fork it and feed your own string into the function!

``````🚀 🚀 🚀 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 
→ Moving 1 into position 

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 
→ Moving 2 into position 

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 
→ Moving 3 into position 

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 
→ Moving 5 into position 

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:

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

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

return prevTwo
}
``````

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