I am attempting to solve a generic Palindrome problem recursively. However, it seems that my algorithm is only evaluating the first recursive call, not the second, which should check all characters in the string. There is apparently a logic error in my algorithm, but I can't spot it. Can anyone advise? See the code below.

function isPalindrome(totalChars: number, lastIdx: number, str: string): boolean | undefined {
    console.log(`lastIdx: ${lastIdx}; char: ${str[lastIdx]}`);

    // const curIdx = lastIdx;
    let highIdx = lastIdx;
    const lowIdx = totalChars-1 - highIdx;

    // Base Case: 
    if(totalChars === 0) return true;
    if (lowIdx === highIdx) return true;
    if (lowIdx > highIdx) {
        console.log(`Endpoint reached; STR: ${str}; LOW: ${str[lowIdx]}; high: ${str[highIdx]}`);
        return;
    }

    if(str[lowIdx] === str[highIdx]) {
        console.log(`Loop through idx; STR: ${str}; LOW: ${str[lowIdx]}; high: ${str[highIdx]}`);
        return true;
    }
    else if(str[lowIdx] !== str[highIdx]) return false;


    // Recursive Case:
    return isPalindrome(totalChars, highIdx, str) && isPalindrome(totalChars, highIdx-1, str);
}


// console.log("a is Palindrome: "   isPalindrome("a".length, "a".length-1, "a"));
// console.log("motor is Palindrome: "   isPalindrome("motor".length, "motor".length-1,"motor"));
console.log("rotor is Palindrome: "   isPalindrome("rotor".length, "rotor".length-1,"rotor"));

CodePudding user response：

There are a few problems:

1. your if...else will always result in a return, and so the statement with the recursive call will never be executed.

   Note that the condition after else if will always be true when it gets evaluated, since it is the negation of the condition that is evaluated in the earlier if statement.

   More importantly, when that earlier if condition is true, you don't want to return, as it has not been verified yet that the remaining (inner) characters match. This still has to be verified via the recursive call, so this is not a place to perform a return. Just remove that if block, and only return when the characters differ.

   So replace this:

       if(str[lowIdx] === str[highIdx]) 
       {
           return true;
       }
       else if(str[lowIdx] !== str[highIdx]) return false;
   

   With just:

       if(str[lowIdx] !== str[highIdx]) return false;
   

2. The first recursive call passes the same arguments as the current execution of the function got -- this will lead to infinite recursion. A recursive call must always make the problem smaller. In this case, there is actually no need to make two recursive calls, and you should remove that first one.

   So replace this:

   return isPalindrome(totalChars, highIdx, str) && isPalindrome(totalChars, highIdx-1, str);
   

   with:

   return isPalindrome(totalChars, highIdx-1, str);
   

3. The base case has a condition where return is executed without boolean return value. The function should always return a boolean value. In this case it should be true, because it means that all character-pairs were compared, and there is no single-middle character remainined (the size of the string is even). So you can combine this case with the previous base case. In fact, that base case condition will also work when totalChars is zero, so you can omit that first if.

   So change this:

   if (totalChars === 0) return true;
   if (lowIdx === highIdx) return true;
   if (lowIdx > highIdx) {
       return;
   }
   

   with:

   if (lowIdx >= highIdx) return true;