DEV Community ๐Ÿ‘ฉโ€๐Ÿ’ป๐Ÿ‘จโ€๐Ÿ’ป

Cover image for Algo Logging: The nth Fibonacci Number in JavaScript
Raquel Romรกn-Rodriguez
Raquel Romรกn-Rodriguez

Posted on

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.

David Rose from Schitt's Creek saying "That's a real quick no"

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);
}
Enter fullscreen mode Exit fullscreen mode

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) {...}
Enter fullscreen mode Exit fullscreen mode
  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 ! 

Enter fullscreen mode Exit fullscreen mode

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[0] + prevTwo[1];
    prevTwo = [prevTwo[1], sum];
  }

  return prevTwo[1]
}
Enter fullscreen mode Exit fullscreen mode

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

Top comments (0)

Classic DEV Post:

Understanding git through images