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:

CodeWars
LeetCode

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

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 nth 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[0] + prevTwo[1].

   show

   
   

   let sum = prevTwo[0] + prevTwo[1];
   

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.

   show

   
   

     prevTwo = [prevTwo[1], sum];
   }
   

5. When the loop is finished, return prevTwo[1]. This is our nth Fibonacci Number

   show

   
   

     return prevTwo[1]
   }
   

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

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

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