Palindrome Recursion Program

Question

public static boolean palindrome(String input, int i, int j)
 {
  if (i >= j)
   return true;
  if (input.charAt(i) == input.charAt(j))
  {
   i++;
   j--;
   palindrome(input, i, j);
  }
  else if (input.charAt(i) != input.charAt(j))
   return false;
 }

My Java platform (eclipse) won't accept this code as working, due to a "lack of return type." Now I know in proper coding ediquite, it's better to use only one return value, but when it comes to recursion, this is somewhat new to me. How can I go about doing this? If I instantiate a Boolean type at the top of this method, it's creating a new instance of that variable (and instantiating it as null or whatever I set it to) each time the method runs, but if I place it above my constructor, my method won't assign a value to it/can't return it.

Basically, how do I go about modifying my code to have a single return value that Eclipse will accept as always executing? I can do this easily enough with loops, but I'm not sure how to approach the topic with Recursion.

Answer 1

You can certainly just do this:

return palindrome(input, i, j);

However it is good practice to have a single return to improve readability. Try this on for size:

   boolean isPalindrome = false; 
   if (i >= j)
   isPalindrome = true;
   else if (input.charAt(i) == input.charAt(j))
  {
   i++;
   j--;
   isPalindrome = palindrome(input, i, j);
  }
  else if (input.charAt(i) != input.charAt(j))
   isPalindrome = false;
  return isPalindrome;
 }

Have that boolean always instantiated. The key here is to make palindrome's return be stored in that boolean.

The recursive portion comes in at the call to palindrome. It will only finally return the final value after all of the recursive calls, because it only ever determines if its a palindrome when it reaches the end of the recursive cycle.

Answer 2

In the second if block, you don't return anything.

Just change the recursive call so that you return its value:

  return palindrome(input, i, j);

Also, incidentally, you don't need to do i++ and j-- in the if block-- you can instead call the palindrome method with i+1 and j-1 instead, and that will have basically the same effect.

Answer 3

The issue is that you have no return inside the second if statement. If charAt i and j are equal you never return anything.

Keeping the spirit of your code I'd shorten the whole thing up to be:

public static boolean palindrome(String input, int i, int j)
{
  if (i >= j)
  {
    return true;
  }

  if (input.charAt(i) == input.charAt(j))
  {
    return palindrome(input, i + 1, j - 1);
  }

  return false;
}

Answer 4

Just for improved readability:

public static boolean palindrome(String input, int i, int j)
{
    if (i >= j)
        return true;

    if (input.charAt(i) != input.charAt(j))
        return false;

    return palindrome(input, i + 1, j - 1);
}

If we could use C# and Linq (since I don't have Java dev environment here) to reversing a char array:

public static bool palindrome(String input)
{
    return input.Equals(new String(input.ToCharArray().Reverse().ToArray()));
}