Computer Science: Recursion

Photo by James Hon on Unsplash

Exordium

The official definition of recursion is “a computer programming technique involving the use of a procedure, subroutine, function, or algorithm that calls itself one or more times until a specified condition is met at which time the rest of each repetition is processed from the last one called to the first.”

Recursion can also be thought of as defining something in terms of itself. Think of when someone defines a word with the word. When recursion is used in computer science, programming, software engineering, etc — it’s used as a way to solve a problem with subsets of that problem. You end up writing a method that uses itself to solve a problem within itself.

As you can imagine, a recursive method has the potential of literally going on forever. Note that it’s imperative to write recursive methods very thoughtfully, as they can become very inefficient.

The example of recursion used here is determining whether or not a string is a palindrome. A palindrome is a string that reads the same backward as it does forward. There are two types of palindromes:

1. Odd-length palindrome
2. Even-length palindrome

An even-length palindrome has two halves. The second half is just the reverse of the first. Out of “5432112345”, the first half is 54321; the second half is 12345.

An odd-length palindrome has three parts; a first half, a central character, and the reverse of the first half. Out of “aibohphobia”, the first half is aiboh, the central character is p, and the reverse of the first half is hobia. (Aibohphobia is the fear of palindromes).

So, how does a recursive palindrome algorithm look? First off, I want to show you the initial version of a “recursive palindrome” method that I wrote while learning about this topic. Then, I want to show you a more efficient version of this method that was shown to me via Stack Exchange’s Code Review community.

When writing recursive methods, it’s good to have a ‘base case.’ This is a case where the method can be evaluated without recursion. Remember that recursion is the act of solving a problem, by solving smaller instances of the same problem, unless the problem is so small that we don’t need to solve it with recursion; a.k.a — we can solve it directly. The base case is where we solve it directly.

A Recursive Palindrome Method in JavaScript

What does the method need to do in order to work correctly?

1. Have a base case that checks if the length of the string is zero or one. If it is, return true, as empty strings and strings with one character are inherently palindromes.
2. If the length of the string is greater than zero or one, obtain the first and last character of the string and compare them to each other. If you compare them to each other and they are not equal to each other, then the string is not a palindrome.
3. If the first and last characters are equal to each other, the string has a chance of being a palindrome. If this is the case, run the method within itself, using recursion to traverse through the string until it eventually returns true or false.

As mentioned, this first method is recursive, but it’s not efficient and doesn’t work with even-length strings. It also doesn’t fulfill the exact steps listed above. The second method will fulfill those steps. Both of these methods are written in JavaScript.

The Inefficient Algorithm

The first thing I did was write two methods that obtained the first and last character of the string. They both run two lines of code and use the slice method.

function obtainFirstCharacterOfString(str) {
    const firstChar = str.slice(0, 1);
    return firstChar;
}
function obtainLastCharacterOfString(str) {
    const lastChar = str.slice(-1);
    return lastChar;
}

Then, these methods get used in a methods named recursivePalindrome. This method has a base case (1) that checks the length of the string, and if it’s zero or one, it returns false. (This is the first error in this version of the algorithm. It does not treat empty strings, or strings with one character, as palindromes as it should. It also does not work with even-length strings, as it slices the string down to zero).

The algorithm then uses the two custom methods (2) to obtain the first and last characters of the string.

Finally, the first and last characters get compared to each other (3).

If they are not the same, the algorithm returns false (4).

If they are the same, then the program control drops into the if statement and checks to see if the string has a length of one (5).

The check is accomplished by slicing from the second character to the last (but doesn’t include the last character. This is due to the nature of the slice method), then comparing the length to one. Using .slice(1, -1) translates to ‘extract the characters from index 1 to the index of the character right before the last character’. Using .slice() like this works for odd-length palindromes, but as I mentioned earlier, it does not work for even-length palindromes. If an even-length palindrome is used as an input, the string will be sliced down until it has a length of zero, then it will return false. It’s also very inefficient to move through the string each time when making this check. Again, this is another issue that will be fixed in the second version of the algorithm.

Suppose racecar is used as an input example. In that case, the algorithm makes the `if (str.slice(1, -1).length === 1)` check, then drops into the `else` clause and returns the recursivePalindrome method; which is of course, recursive. The method would end up slicing down to e, and returning true.

If the length is greater than zero, then the recursivePalindrome method is called, and the process is essentially restarted (6). Again, the string is sliced, using .slice(1, -1). The slice method obtains the next two letters, moving inward from the left and right sides of the string; from the beginning and end. Using racecar as an example again, the first time the recursive method is called, the parameter ends up being aceca, and the method runs again using this new string.

function recursivePalindrome(str) {
    // 1
    if (str.length === 0 || str.length === 1) {
        return false;
    }
    // 2
    const firstChar = obtainFirstCharacterOfString(str);
    const lastChar = obtainLastCharacterOfString(str);
    // 3
    if (firstChar === lastChar) {
        // 5
        if (str.slice(1, -1).length === 1) {
            return true;
       } else {
           // 6
           return recursivePalindrome(str.slice(1, -1));
       }
    } else {
        // 4
        return false;
    }
}

Now for some basic ‘tests’. Here are the properties that have been saved to run the tests on:

// Odd-length palindromes
const racecar = ‘racecar’;
const deified = ‘deified’;
const aibohphobia = ‘aibohphobia’;

// Even-length palindromes
const oneTwoThree = ‘123321’;
const oneTwoThreeFour = ‘12344321’;
const oneTwoThreeFourFive = ‘1234554321’;

// Even-length non-palindromes
const honeybee = ‘honeybee’;
const bumble = ‘bumble’;
const wasp = ‘wasp’;

// Odd-length non-palindromes
const apple = ‘apple’;
const tesla = ‘tesla’;
const zymergen = ‘zymergen’;

Now, the ‘tests.’

console.log(recursivePalindrome(racecar));
console.log(recursivePalindrome(deified));
console.log(recursivePalindrome(oneTwoThree));
console.log(recursivePalindrome(oneTwoThreeFour));
console.log(recursivePalindrome(apple));
console.log(recursivePalindrome(tesla));
console.log(recursivePalindrome(honeybee));
console.log(recursivePalindrome(bumble));

These tests are not proper tests, as there is no way to pass in what should be expected as a parameter. Yet another issue that will be fixed in the second version of the algorithm.

The time complexity of this algorithm is O(n²). Meaning it has a quadratic runtime, which is slow. If there are 100 items, it does 10⁰² units of work; 10,000 total units of work. If you were to compare this to an algorithm with linear runtime, the quadratic algorithm would be two times slower. If you then doubled the items in the quadratic algorithm from 100 to 200, the algorithm would run four times slower than when it did with 100 items. It would produce four times the amount of units of work, equating to 40,000 units of work. Why is this important? Because efficiency is a vital aspect of computing.

Sometimes, an algorithm must be written with a particular asymptotic analysis (usually in the context of Big O notation) due to various constraints. These constraints include the types of data structures being worked with and what is trying to be accomplished within the algorithm.

The next algorithm is written much more efficiently and hits the three points mentioned earlier about what is needed to successfully examine a string, and determin whether it is a palindrome.

The Efficient Algorithm

I did not write this version of the algorithm. It was shown to me via the power of the internet and Stack Exchange’s Code Review community after posting the original algorithm for review. The solution provided goes into more than what I do here, as the author also shows how to write the algorithm entirely without recursion. Doing so improves the memory complexity of the algorithm because the calls to the recursive method don’t get stacked.

Here are the things from the previous version of the algorithm that need to be fixed:

• The base case checks the length of the string but does not treat empty strings, or strings with one character, as palindromes.
• The check that uses .slice(1, -1). This checks if the string length is one and, if so, returns true. Remember that the use of .slice(1, -1) in this context is inefficient as it searches through the entire length of the string each time it runs.
• The use of str.slice(1, -1) as a parameter of the call to recursivePalindrome. Note that .slice() returns a new string, it doesn’t just modify the original. Because of recursion, these new strings get added to the memory each time the method is called.

In addition to the fixes above, this version of the algorithm will meet the following ‘restrictions’:

1. Have a base case that checks if the length of the string is zero or one. If it is, return true, as empty strings and strings with one character are inherently palindromes.
2. If the length of the string is greater than zero or one, obtain the first and last character of the string and compare them to each other. If you compare them to each other and they are not equal to each other, then the string is not a palindrome.
3. If the first and last characters are equal to each other, the string has a chance of being a palindrome. If this is the case, run the method within itself, using recursion to run through and search the string until it eventually returns true or false.

These ‘restrictions’ ensure that the algorithm truly uses recursion to check if a string is a palindrome.

This version of the algorithm consists of one method that holds another method; two methods, one nested inside the other. The algorithm removes the two methods found in the previous version that obtained the first and last character of the string. Though these two methods use .slice(), they do not increase the algorithm’s time complexity, as they always take the same time to complete. Removing the methods is driven out of conciseness rather than improving efficiency. The time complexity of .slice() depends on how it gets used.

Here are the steps of the more efficient version of recursivePalindrome:

1. Create a method named isPalindrome that does the following:
2. Checks if the value of last minus first is less than one. If it is, return true. This is the check to see if the length of the string is less than one. Right at the beginning of the algorithm, there’s a check to see if the string has a length of less than one and, if so, treat it like a palindrome.
3. The next check is to see if the character at the index of first is not equal to the character at the index of second. If the first string is not equal to the last, then the method returns false. Otherwise, the string has a chance of being a palindrome. This step will ultimately determine if a string is a palindrome.
4. If the string has a chance of being a palindrome, the isPalindrome() method is called. The parameters passed are first+1, and last-1. Each time this method is called, the first and last variables increment positively and negatively by one. Then, with these values, the isPalindrome() method is called. This is the recursive aspect of the method. Remember that first and last are not the actual characters of the string; they are numbers that are used as indices to obtain the characters of the string.
5. Return a call to the isPalindrome method, with a starting character at the 0th index, and the last character at the string.length — 1 index. This is only called once. Then, everything else needed to determine if the input is a palindrome happens recursively within the isPalindrome method.

function recursivePalindrome(string) {
    // 1.
    function isPalindrome(first, last) {
        // a.
        if (last — first < 1) {
            return true;
        }
        // b.
        if (string[first] !== string[last]) {
            return false;
        }
        // c.
        return isPalindrome(first+1, last-1);
    }
    // 2.
    return isPalindrome(0, string.length — 1);
}

The algorithm now has a runtime of O(n), a.k.a, linear. An algorithm with a linear runtime will complete as many units of work as the number of items in the input. For example, if the input is 100 items, the algorithm will complete 100 units of work. This time complexity is much more efficient than a quadratic time complexity. One thing that contributes to this is that the original string is traversed through to obtain two characters at a time. It does this by simultaneously moving from the beginning and end of the string, toward the center of the string. It never returns a new string, but simply uses the original string the entire time.

Now, to write a proper test for the algorithm. The test takes two parameters, input and expect, and it contains two if statements. The first if statement checks to see if expect is true, and output is false. If the output is false, and ‘true’ is passed in as the expect parameter, then the test was not expecting the string to be a palindrome. The second if statement checks to see if expect is false, and output is true. If the output is true, and ‘false’ is passed in as the expect parameter, then the test was expecting the string to be a paldinrome.

function testPalindrome(input, expect) {
    const output = recursivePalindrome(input);
    if (expect && !output) {
        console.error(`Expected ${input} not to be a palindrome.`);
    }
    if (!expect && output) {
        console.error(`Expected ${input} to be a palindrome.`);
   }
}

Using racecar as an example for the test, one can see how the testPalindrome() method works. The first parameter is racecar, and the second parameter is false. This means that the test is going to expect an output that is not a palindrome; therefore, it will print the error message to the console since racecar is a palindrome.

testPalindrome(racecar, false);

Here’s the output:

Odd-length palindromes
Expected racecar to be a palindrome.
Even-length palindromes
Odd-length non-palindromes
Even-length non-palindromes

Here is a more robust suite of tests:

// Odd-length palindromes
console.log(‘Odd-length palindromes’);
testPalindrome(racecar, false);
testPalindrome(deified, true);
testPalindrome(aibohphobia, true);
console.log(“”);
// Even-length palindromes
console.log(‘Even-length palindromes’);
testPalindrome(oneTwoThree, false);
testPalindrome(oneTwoThreeFour, true);
testPalindrome(oneTwoThreeFourFive, true);
console.log(“”);
// Odd-length non-palindromes
console.log(‘Odd-length non-palindromes’);
testPalindrome(apple, true);
testPalindrome(tesla, false);
testPalindrome(zymergen, false);
console.log(“”);
// Even-length non-palindromes
console.log(‘Even-length non-palindromes’);
testPalindrome(honeybee, true);
testPalindrome(bumble, false);
testPalindrome(wasp, false);
console.log(“”);

To recap, this version of the algorithm has a time complexity of O(n). The issues from the first version of the algorithm have been fixed. Plus, it meets all the requirements to recursively determine if a string is a palindrome.

— — —

Thank you for reading. You can find the code that goes along with this post on GitHub.

Additional Resources:

• Memory complexity? — Stack Exchange, Computer Science
• Recursive Plaindrome in JavaScript — Stack Exchange, Code Review