Recursion

Recursion. I remember a time when that word struck fear in my heart. "Why would anyone want to use recursion instead of a loop to solve a problem?" I thought to myself. Due to this being a crux of mine for such a long time, I decided to dive in, do some research, and conquer my fear of overflowing the call stack.

Recursion: 1 part ending conditional, 1 part changing input

The most important two parts of solving a problem recursively are getting the ending conditional correct and changing the input to the recursive function with each additional call. Don't worry if this doesn't make sense. We'll go over a few examples and hopefully you'll see the pattern.

Iteration VS Recursion

It's important to understand that typically you can solve certain problems in two different ways: with recursion or by looping. Looping has always seemed more straightforward to me and maybe that's because it is what is typically taught first. Let's look at an example solved first by looping, and then the same problem solved recursively.

Value in an Array

Let's write a function that takes an array and a value and checks if that value exists in the array. If it does, we will return true, if not, we will return false.

// looping
function includes(array, value) {
    for (val in array) {
        if (val == value) return true;
    }
    return false;
}

This is a very natural feeling solution to me. We loop through each value in the array, checking if the argument passed in matches any of our array's values. If no match is found, we return false.

Now let's look at the same solution but solved through recursion.

// recursion
function includes(array, value) {
    if (arr.length == 0) return false;
    return arr[0] == val || includesNumber(arr.slice(1, arr.length), val);
}

This solution does not seem as natural, to me at least, but it is just as valid as a solution as the previous iterative solution. In this example we can clearly see the two parts of recursive solutions:

1. If our array is empty we have no reason to continue calling our function and should return false. After all, reaching the end of the array doesn't mean we have found a match. This is our ending conditional.
2. The next part is slightly less intuitive. We need to check if the beginning or our array is equal to our given value. But we also need to check the rest of the array by calling our includes function, but if we supply the same array, we will just keep checking the first same element and overflow the call stack. Like I stated earlier, we need our input to change. Because we have already checked the first element in the array, we can now call includes again but this time with that first element removed by slicing the array. Now, the next time we call includes we will check the first element of our new slice, which will really be the second element. We use the || operator because we only need to know if one of our calls to includes returns true.

Reverse a String

Next, let's go ahead a solve the age old problem of reversing a string.

function reverseString(str) {
    if (str.length == 1) return str[0];
    return str[str.length - 1] + reverseString(str.slice(0, str.length - 1));
}

Here again we can see the pattern of an ending conditional and changing our input with each call.

1. If our string has only 1 character we should return it and end the recursion.
2. Initially we want to return the last character of the string and then add the next last character. To get that next last character we need to call our function again, but this time remove the last character from our string before we call the reverseString function again. We do this over and over again until we reach our ending conditional.

Check if a String is a Palindrome

For our final example, let's write a recursive function that checks if a string is a palindrome.

function isPalindrome(str) {
    if (str.length <= 1) return true;
    return str[0] == str[str.length - 1] && isPalindrome(str.slice(1, str.length - 1));
}

1. For our ending conditional we are going to return true if we get to a string length of either 0 or 1, because a palindrome with an odd number of characters will have a middle character with no matching character. And if we reach the end of the string, eg. str.length == 0, then we can return true.
2. For each call we want to check the first and final character of our string and make sure they match. And for our word to be a palindrome we need that expression to return true AND the following calls to be true. Again, with each additional call we want our argument to change. This time we are removing the first and final characters from the string with each call.

Conclusion

Recursion can be confusing, but just take your time with it and solve a few problems in your free time. If something goes wrong, look at the 2 parts. Most likely, the ending conditional is wrong or the input isn't being changed correctly.