Recursive Palindrome in JavaScript

Question

Would someone review this code, and confirm that it is indeed recursive? I'm learning computer science and going through different types of algorithms. Right now, I'm focusing on recursion want to ensure that this 'recursive palindrome' method is truly recursive. I've passed six different strings as a test, three that were palindromes and three that were not. The method worked as expected, but again; I'm really looking for a cross-check to ensure this is recursive.

From my understanding, when writing recursive algorithms, the base case should take care of the end of the recursive process. Or, in other words, it should solve the very last sub-problem of the algorithm, after all the recursion has taken place. Please correct me if I am wrong in that thinking.

My observation here is that at some point, the string will end up with 1 character no matter what. Again, the base case should take care of that, but it doesn't. That is why I added the if (str.slice(1, -1).length === 1) check inside of if (firstChar === lastChar). If the method breaks the word down and it is one character and a palindrome, then it will return 'String is a palindrome.' This can be verified when passing 'racecar' as a parameter of the method.

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

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

function recursivePalindrome(str) {
    // Base case
    if (str.length === 0 || str.length === 1) {
        return 'String is not a palindrome';
    }

    const firstChar = obtainFirstCharacterOfString(str);
    const lastChar = obtainLastCharacterOfString(str);

    if (firstChar === lastChar) {
        if (str.slice(1, -1).length === 1) {
            return 'String is a palindrome';
        } else {
            return recursivePalindrome(str.slice(1, -1));
        }
    } else {
        return 'String is not a palindrome';
    }
}

Answer 1

You really didn't need to include the second snippet that you know is not working.

However, the first snippet is not working correctly either although you thought it does. That's because you didn't write enough tests. The main problem with your implementation is that is treats empty strings and one letter words as non palindromes. But they actually both are palindromes, thats all you need to fix your implementation and actually it would fix the second snippet too.

Now for some more detail about your code.

Don't return human readable text from functions that basically want to return a boolean.

Asking if length is 0 or 1 can be simplified to asking if it is less then 2.

Slicing a string to get character at certain position is quite ineffective, instead you can just access individual chars using square brackets or charAt method. I'd prefer the bracket access because the algorithm can then also tell if arrays are palindromic, not just strings. The slicing of the input to create n strings of length 1 increases the memory required by the algorithm to O(n) although it already is O(n) because of the recursion but it increases the scale anyway.

Also slicing the string to get the input for next recursion step is ineffective and not necessary. Instead you could pass around the entire string and index of currently examined character. The slicing is degrading the time complexity to O(n²) and memory complexity also to O(n²).

For the matter of efficiency I also recommend to avoid recursion entirely but I'll assume recursion is the subject of study here...

function isPalindrome(input) {
  function isPalindromeDetail(first, last) {
    if (last - first < 1) return true
    if (input[first] !== input[last]) return false
    return isPalindromeDetail(first+1, last-1)
  }
  return isPalindromeDetail(0, input.length-1)
}

function testPalindrome(input, expect) {
  const output = isPalindrome(input)
  if (expect && !output) console.error('Expected ', input, ' to be palindrome')
  if (!expect && output) console.error('Expected ', input, ' not to be palindrome')
}

testPalindrome('', true)
testPalindrome('a', true)
testPalindrome('aa', true)
testPalindrome('aba', true)
testPalindrome('abba', true)
testPalindrome('abcba', true)

testPalindrome('ab', false)
testPalindrome('abc', false)
testPalindrome('abbc', false)
testPalindrome('abcab', false)

testPalindrome([1 ,2, 1], true)
testPalindrome([1, 2, 3], false)

PS: I am writing on mobile and haven't tested the code...

PS2: in the above snippet you see that the inner isPalindromeDetail is accessing the input variable from the outer scope rather than having it passed as argument. The same can be done for the first and last variables which only proves that it really doesn't need to be recursive because there is no state that needs to be stacked up. In the recursive form without slicing above we have time complexity O(n) and memory complexity also O(n). In the nonrecirsive form below we have time complexity O(n) and we reduced the memory complexity to O(1) just by not stacking the recursive calls.

function isPalindrome(input) {
  let first = 0
  let last = input.length - 1
  while (first < last) {
    if (input[first] !== input[last]) return false
    ++first
    --last
  }
  return true
}