A Few Exercises for Learning Recursion

Cover Photo by Tine Ivanič on Unsplash

In Javascript, functions carry the load. Every developer must be comfortable writing code that distributes the work using functions if they have any hope of the code being readable. Of course, there's also the directive to write code remains "DRY" (Don't Repeat Yourself).

Eventually, our problem-solving efforts require recursive functions. This simply means that the function has to call itself. I have to admit, the thought of writing recursive functions was uncomfortable. It seemed like so much could go wrong and that I would end up in an endless loop.

The concept of recursion at first seemed complicated to my way of thinking. In life, if I want to accomplish a task, I process that task as a whole unit. I consider eating a bowl of cereal or folding the laundry as a single task.

If I consider those same tasks with recursion in mind, then I have to divide these tasks into a base case and recursive call. To eat a bowl of cereal, I call the eatCereal function. That function will return a base case of "done" if the bowl is empty. Otherwise, it will take a single bite and call itself again. Likewise, to fold laundry, I call the foldLaundry function. This returns a base case of "folded" once I'm out of laundry, or folds a shirt and then calls itself again.

The base case is very important. It defines the last step of the recursive function and provides a way out. If this is omitted or improperly considered, then we're in an endless loop or causing a memory overflow error.

To provide an opportunity to review recursive functions in action, I coded three examples. These functions will:

1. reverse a string
2. test a string to see if its a palindrome
3. test an array to see if it includes a particular element

Reverse a String

This function accepts the string parameter, then returns that string in reverse order.

I wrote the function to extract the last character of the string and then append the result from calling itself again. If there is only one character left, then just return the last character.

function reverseString(myString) {
    const lastLetter = myString[myString.length - 1]
    if (myString.length > 1) {
        return lastLetter + reverseString(myString.substring(0, myString.length - 1));
    } else {
        return lastLetter;
    }
}

Palindrome Test

Who doesn't love a palindrome? This function returns true if the string parameter is spelled the same both forward and backward, and false if it isn't.

My solution will test to see if the first and last characters are equal, and then call itself again with the inner characters. It will return true if the string only has one character (for odd number string lengths), or if there are only two identical characters. Otherwise, it returns false.

function isPalindrome(myString) {
    // if outside are the same and inside is a palindrome 
    if (myString.length === 1) {
        return true;
    } else if ((myString.length === 2) && (myString[0] === myString[1])) {
        return true
    } else if (myString[0] === myString[myString.length - 1]) {
        return isPalindrome(myString.substring(1, myString.length - 1))
    } else {
        return false
    }

}

Test Array for Included Number

The last function accepts an array and the element we're searching for as parameters. The function will return the true if the array includes the supplied element.

To handle this recursively, the function will return true if the first element matches. If not, then it will call itself with the first element removed. The base case returns false once the length of the string is 0.

function includesNumber(myNums, element) {
    if (myNums.length >= 1) {
        if (myNums[0] === element) {
            return true
        } else {
            return includesNumber(myNums.slice(1), element)
        }
    } else {
        return false
    }
}

Understanding the solutions to these three examples helped me to calm down and feel confident about my ability to write recursive functions. It also aids in my ability to handle more complex situations and algorithms. I hope these assist others as well.

Happy coding!