Recursive implementation of palindrome string checker

Question

I've tried to refactor my program to single return statement at the end of the program, however, it ruins the end statements of the recursion because I want to return from function in specific line and not in the end of the function.

I'd like suggestions on how this code can work and be elegantly designed to comply with

1. Multiple return statements
2. Single return statement

private static boolean isPalindrome(String pal)
{ 
 if(pal.length() == 1 || pal.length() == 2 )
 {
 if(pal.length()==1)
 {
 return true;
 }
 else
 {
 if(pal.charAt(0) == pal.charAt(1))
 {
 return true;
 }
 return false;
 } 
 }
 else
 {
 if(pal.charAt(0) == pal.charAt(pal.length()-1))
 {
 return isPalidrome(pal.substring(1, pal.length()-1));
 }
 return false;
 }
 }
}

Answer 1

For all practical purposes, recursion is a bad idea for this problem, mainly because String.substring() is an expensive operation, especially since Java 7. Let's assume that you're doing this just as a fun educational exercise.

Single return statements are overrated. There's no practical advantage to forcing your code to have just one return for its own sake.

Your base cases are poorly chosen. A zero-length string will cause a crash. If you handle empty strings as a base case, then you no longer need to treat two-character strings as a special case.

You take the string length often enough that it's worth assigning it to a variable.

Overall, the function could be written more compactly.

public static boolean isPalindrome(String s) {
 int len = s.length();
 if (len <= 1) {
 return true;
 }
 return (s.charAt(0) == s.charAt(len - 1)) &&
 isPalindrome(s.substring(1, len - 1));
}

• Marc-Andre: The single return "rule" make you write weird code IMO. Most of the time you will either have a variable to return at the end (so it's only purpose will be to return the result) or a lot of nested if.
• Cruncher: If you're concerned about substring being slow, you can make a private method that takes a char[] and int start, int end
• Cruncher: If OP really wants a single return statement, they can do this with: return (len <= 1) || (s.charAt(0) == s.charAt(len - 1)) && isPalindrome(s.substring(1, len-1));
• mardavi: The single return rule is not to be intended as a single return statement in a method, but rather as a single logical exit point from a code block. Meaning, something like for(int i = 0; i < 100; i++) { if(i==50) break; else //whatever is considered bad (it makes the code harder to read), since the for-loop has more exit points, while the provided OP's code, for what concerns returns, is actually perfectly fine.
• 200_success: @mardavi Single return is still overrated. There's not much to be gained by requiring a single exit point for loops either.

Answer 2

It seems to me that if you're going to do this, it's worth avoiding all those substring calls, since they're pretty slow. It ends up almost simpler without them anyway.

private static boolean isPalindrome(String pal) {
 return isPalindromeImplementation(pal, 0, pal.length()-1);
}
private static boolean isPalindromeImplementation(String pal, int start, int stop) { 
 if (stop - start <= 1)
 return true;
 return pal.charAt(start) == pal.charAt(stop) &&
 isPalindromeImplementation(pal, start+1, stop-1);
}

Using substring every recursive call means the function takes \$O(N^2)\$ time and space. By avoiding that, this reduces both the time and space complexity to \$O(N)\$ instead--some constant amount for the stack frame at every invocation. With a compiler that implements tail recursion elimination, it should be trivial to reduce that to \$O(1)\$ space and \$O(N)\$ time complexity (which I'm reasonably certain is the best you can hope for).

• Cruncher: which I'm reasonably certain is the best you can hope for If somebody can solve palindrome in less than O(n) I'll quit using a computer forever.
• Jerry Coffin: @Cruncher: Although I can't point to a specific algorithm to do it, I can just about imagine a quantum computer being able to do this in less than O(N). Probably likewise on a highly parallel computer. But yes, on a serial computer, I think O(N) is about the best you can hope for.

Answer 3

Your code, and whole question is based on the assumption that methods should have a single return statement. This 'prejudice' is not significant in Java (there are other languages where it makes sense). In terms of code-style, it is common in Java, and best-practice too, to have multiple exit points from methods, including multiple return statements (The other exit path being thrown exceptions).

In addition, your question asks how to improve the recursive method. If I was asked to review this code in a real review, I would say: "Don't solve this problem with recursion!".

Problems with recursion:

1. limited stack depth (someone gives you a 1MB palindrome String to check!)
2. iteration is simpler and faster
3. less stack management and garbage.

So, my suggestions is: recursion is not the best solution to this problem. A simple loop will suffice:

private static boolean isPalindrome(String pal) {
 final int last = pal.length() - 1;
 for(int i = last / 2; i >= 0; i--) {
 if (pal.charAt(i) != pal.charAt(last - i)) {
 return false;
 }
 }
 return true;
}

The above code will be far more efficient than the substring option as well. It is also 'fail-fast', and exits on the first non-palindrome characters.

Answer 4

Simplification time!

if(pal.charAt(0) == pal.charAt(1))
{
 return true;
}
return false;

Can become:

return pal.charAt(0) == pal.charAt(1);

---

if(pal.charAt(0) == pal.charAt(pal.length()-1))
{
 return isPalidrome(pal.substring(1, pal.length()-1));
}
return false;

Can become:

return pal.charAt(0) == pal.charAt(pal.length()-1) &&
 isPalidrome(pal.substring(1, pal.length()-1));

---

Now, what about an empty string? At the moment, this would cause an exception because the code would run pal.charAt(0).

Therefore it would be better to check pal.length() <= 1 first and return true if that's the case.

You can also remove all else because you're returning inside all the if-statements.

After changing the braces style to use { on the same line instead of it's own line (to adhere to the Java conventions), this leaves us with:

private static boolean isPalindrome(String pal) {
 if (pal.length() <= 1) {
 return true;
 }
 if (pal.length() == 2) {
 return pal.charAt(0) == pal.charAt(1);
 }
 return pal.charAt(0) == pal.charAt(pal.length() - 1) &&
 isPalidrome(pal.substring(1, pal.length() - 1));
}

Now, even though this can be rewritten using a ternary operator, I wouldn't recommend it because it would end up being quite unreadable. Actually, I'm a bit skeptic already at the last return line.

Actually, I believe that the if (pal.length() == 2) check is unnecessary, as that's already covered in the last return statement (it would call the function once more for an empty string, which now returns true).

So if you really want just a one-liner for this:

return pal.length() <= 1 ? true :
 pal.charAt(0) == pal.charAt(pal.length() - 1) &&
 isPalidrome(pal.substring(1, pal.length() - 1));

Not the prettiest one-liner I've ever seen, but I believe it works. Personally, I'd prefer a non-one-liner for this method. Writing code on one line just because you can isn't always the best option.

Note that this uses the Ternary Operator, which you should read up on to make sure you understand it in case you haven't seen it already.

Edit:

As correctly stated by Josay in the comments below, the ternary operator can be re-written once more using boolean OR:

return pal.length() <= 1 || (
 pal.charAt(0) == pal.charAt(pal.length() - 1) &&
 isPalidrome(pal.substring(1, pal.length() - 1)) );

Note however that now I'm adding parenthesis around the last statement, as I don't like mixing || with && on the same line.

Once again though, consider the readability differences to this line compared to my previous non-one-liner rewrite, or compared to @200_success' answer.