Learning Recursion

All the challenges and solutions in this post can also be found on my Github repository. If you have other solutions you'd like to share, please feel free to contribute to the repo!

Introduction

First off, I'd like to introduce myself! My name is Jason. I graduated with an associate degree in computer programming back in 2019. Since then, I've dabbled in development here and there, unsure of what I really want to do with my career. I've tried out game development, which is extremely enjoyable and something I'd certainly like to come back to in the future. However, web development is something that always seems to creep up on me. Maybe it's because I've had the most exposure to it, but my favorite part about it is being able to help businesses thrive. I'm an advocate for small businesses and in this day and age, websites are a must for a business to succeed.

On that note, I've started creating a new habit that I call, "Weekly focus". Every week, I pick a specific topic to deep dive into to learn as much as I can. This allows me to slow down and learn how to truly understand concepts I've previously learned. I try to pick topics that are difficult to learn or are important for everyday programming. Along with it, I plan to write a post about everything I learn each week. This will help me lock in my learnings, while hopefully helping others learn as well.

---

This week's focus is Recursion using JavaScript.

This week, I completed four recursion challenges. Three of them didn't spark a lot of extra thinking, but they certainly helped with understanding how recursion works. The four challenges I completed were calculating the sum of natural numbers, calculating the value of an exponent, calculating Fibonacci numbers (this one is interesting) and lastly, calculating the sum of an array. For the sake of post length, I will only go over two of these.

Challenge 1: Calculate Sum of Natural Numbers

The goal is to calculate the sum of all numbers leading up to a number of your choosing. For example: 1 + 2 + 3 + 4 = 10

This was a great challenge to start with. It had been at least a couple weeks since learning about recursion, so this was perfect. I had to use some help to figure it out, but this set me up for the following challenges. Let's break it down!

To start, you'll need a function that calls itself and a base case to determine when it should stop. Without it, your function will loop indefinitely.

Since our goal is to find the sum of a number, we'll want the function to stop looping once our number reaches 0.

function sum(num) {
     if (num === 0) {
         return 0;
}

Next, we need to subtract 1 from our number and add it to our current number (ie. 4 + 3).

num + (num - 1)

This line takes the current number and adds it to the current number minus 1. We also need to call the function within itself to create our loop. To do this, we'll just use "(num - 1)":

num + sum(num - 1)

Complete code:

function sum(num) {

    // Base case - This determines when loop stops
    if (num === 0) {
        return 0;
    } 

    // Adds num to itself minus 1 and creates recursion
    return num + sum(num -1);
}

console.log(sum(4));

Here's a great image I found that shows how recursion works in the background using multiplication:

Shubham Gautam (https://www.enjoyalgorithms.com/blog/recursion-explained-how-recursion-works-in-programming)

---

Challenge 2: Find the nth Fibonacci Value

The goal of this challenge is to create a function that returns the value of nth Fibonacci sequence.

I messed around with this one a bit, so we'll go over the recursive solution and the iterative solution. According to @codeguppy (https://dev.to/codeguppy/practice-recursion-in-javascript-with-these-8-coding-challenges-for-beginners-25bm) the iterative solution is much faster than the recursive solution, so I decided to test this out!

This one took me a bit as I wasn't familiar with Fibonacci sequences, so I learned more than just a programming concept! Due to the nature of Fibonacci sequences, this solution required calling a function within itself twice. We also needed to define two base cases.

function fibonacci (num) {
   if (num === 0) {
       return 0;
   }

   if (num === 1) {
       return 1;
   }
}

Next, we need to call a function within itself, twice. One for (num - 1) and one for (num - 2). We also need to add these two numbers together and return them.

return fibonacci(num-1) + fibonacci(num - 2);

Complete Code:

function fibonacci (num) {

    if (num === 0) {
        return 0;
    }

    if (num === 1) {
        return 1;
    }

    return fibonacci(num - 1) + fibonacci(num - 2);
}

Behind-the-scenes, this would look something like this:

(https://understandingrecursion.readthedocs.io/en/latest/10%20Fibonacci%201.html)

Comparison: Recursive VS. Iterative Solution to Fibonacci Sequence

Due to the focus of this section, I will leave the complete iterative solution at the end without stepping through the code.

I decided to pit the recursive solution against the iterative solution to see the performance difference. Almost immediately, I determined that the recursive solution is not the best solution for this problem. For more information on how recursion calculates Fibonacci sequences and other problems, please refer to Enjoy Algorithms' fantastic article about understanding recursion.

To test the speed of each solution, I ran fibonacci(30) and increased each run by 1. At the 36 mark, the recursive solution started to struggle, taking less than 1 second to load. Once I hit 40, it took about 1 second. At 43, it took over 1 second. By the time I hit 50, it couldn't load within several minutes.

On the contrary, the iterative solution could calculate 50 without hesitation. I decided to take it much farther by testing 1000 and it was able to calculate it immediately.

It's clear that the iterative solution is the way to go when it comes to calculating Fibonacci sequences. The only real benefit, in my opinion, to using a recursive solution is readability. That is not enough to justify the performance issues, however.

Complete Iterative Solution

function fib (num) {

    let fib_zero = 0;
    let fib_one = 1;

    if(num === 0) {
        return fib_zero;
    }

    if (num === 1) {
        return fib_one;
    }

    let fib;
    for (let i = 2; i <= num; i++) {
        fib = fib_zero + fib_one;

        fib_zero = fib_one;
        fib_one = fib;
    }
    return fib;
}