Intro to Recursion in JS

If you are just starting out in programming, you may have heard of this topic; Recursion. Personally, recursion is one of those programming concept’s that has taken me a long time to wrap my head around. Admittedly, I still have a ways to go but in my opinion, there are a few main reasons as to why this topic can be so fleeting.

1) You can solve any problem without Recursion, so it is often looked over for beginners.
2) It’s advantages are not super obvious.
3) It can be flat out confusing.

A good friend of mine once wrote, “Similar to a dictionary using a word to describe itself, it can be frustrating to comprehend. Recursion is unintuitive. When first introduced to recursion, programmers are typically reminded of the movie Inception.”

I may be shamed for this and I probably deserve it, but I am yet to watch Inception. It was just one of those things I never got around to… Maybe it’s why I’ve taken so long to figure the whole recursion thing out ><.

I would say that the main advantage of recursion is that for some longer problems it makes the algorithm a little more readable and elegant. However, for the most part recursion can be slower, and takes up more of the call stack as well.

Here’s a great article that explains some differences between recursive and iterative solutions!

Please bear with me as I take you through a few key terms and some basic problems to help you on your way to mastering the daunting topic of recursion.

Maybe I should have defined it earlier, but Recursion is a function that calls itself until a specified condition is met.

If we wanted to write a function that counted down from a number, we could do something like this.

function sayDownFrom(n){
    console.log(n)
    if(n > 1){
        sayDownFrom(n -1) // recursive call
    } else {
        return true // base case
    }
}

Here in the body of the function we see that the function actually calls itself. This is referred to as the recursive call. We can also see that the function has a stopping point, which can be referred to as the base case. Without a base case, we would end up in an infinite loop.

So, what is this function doing exactly?

Line by line…

function sayDownFrom(n){
    // we print the number first
    console.log(n)
    // then we check if n is greater than 1, which is essentially setting a counter to stop if it is less
    if(n > 1){
        // if n is greater than 1, we call our function which will print out the number before n (in essence, counting down)
        sayDownFrom(n -1) // recursive call
    } else {
        // if n is not greater than one it will go to our base case here and return true and complete the execution
        return true // base case
    }
}

Now, let’s go through a few more problems line by line to get some more experience and see if we can pick out any recurring themes in recursive solutions.

Let's write the classic isPalindrome solution recursively. Here we want to find if the string passed into our function is a palindrome... like "racecar" or "hannah".

function isPalindrome(str) {
    // setting a variable to the length of our string
    var strLen = str.length;

    //checking if the length is zero or if the length is 1
    if (strLen === 0 || strLen === 1) {
      //if we reach either of these cases we will want to return true because of our next 'if' statement
        return true;
    }

    if (str[0] === str[strLen - 1]) {
      // here we are checking if the first index in the string and the last index in the string are the same

      // if they are the same then we are going to make our recursive call, but this time pass in the string without the letters that we just checked for
      // hence the use of slice
        return isPalindrome( str.slice(1, strLen - 1) );
    }

    // if this last 'if' statement were to fail and neither of the first or last letters were equal to each other at any time in our functions life
    // then we would return false immediately since it would not pass the 'if' statement above
    return false;
}

We have looked at two solutions, one with an integer and one with a string. Let's throw one in with an array!

Let's write out a function to see if an array includes a given element.

function includesNumber(arr, element) {
  //if there are no more elements in the array, then we have checked them all and it is not there
  if (!arr.length) {
    // so we will return false
    return false

    // we are now checking if the first element is equal to the passed in element
  } else if (arr[0] === element) {
    // if it is we return true
    return true

    // if none of those things are true yet, we check the array without the first element that we had just checked
  } else {
    return includesNumber(arr.slice(1), element)
  }

Conclusion

We can see some patterns in these few simple problems, particularly our includesNumber and isPalindrome functions. In both we check for equivalents and use the .slice method. Just like anything in programming, you will find patterns the more that you practice. If you are practicing algorithms, I would always recommend finding the solution first (no matter how lengthy and ugly it is) and then refactoring from there (including thinking about or attempting the problem recursively).

Hopefully walking through a few problems has given you a general idea of a few things to look for and how to start thinking about recursive solutions. Cheers!