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)); } 

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).

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.