title: Need some help in writing a recursive implementation for my Palindrome app
body: <p>First of all I am not asking for people to "do my homework" like I have seen others on here ask for. I have managed to code a working iterative version of a program that determines if a string is a palindrome or not. Spaces, punctuation and special characters are ignored while determining if the string is a palindrome. This version does work but when I try and apply recursive statements in the "isPalindrome()" method I get Stack Overflow errors. I know what these errors are, it's just that applying a recursive method in a program like this is quite hard for me to get my head around (I only got taught about them 2 weeks ago). Anyway here is the code I have managed to compile (and run) so far:</p>
  
  <hr>
  
  <pre><code>/** Palindrome.java: A sigle application class that determines if a word or a string
    * is a palindrome or not. This application is designed to ignore spaces between
    * chars, punctuation marks and special characters while determining if the word or
    * string is a palindrome or not.
    * 
    **/
  
  import java.util.Scanner;
  import java.util.StringTokenizer;
  import java.util.regex.*;
  
  public class Palindrome{
  
    static String palindrome, str, str2, str3;
  
    /** The main method of the Palindrome application. Takes input from the
      * user, removes spaces from their input, turns their string input into
      * lowercase and then all non letter characters are taken out of the user's
      * input. Finally the recursive method determines if the string entered in
      * by the user is a palindrome.
      * 
      * @param args Takes in a string array of arguements
      **/
    public static void main(String[] args){
      Scanner input = new Scanner(System.in);
      while(input.hasNext()){ 
        str = removeSpaces(input.nextLine());
        str2 = str.toLowerCase();
        str3 = normalise(str2);
      }
      System.out.println(isPalindrome(str3));
  
    }
  
    /** The default constructor
      **/
    public Palindrome(){
    }
  
    /** isPalindrome(): A boolean method that is passed through a String input
      * and uses a for loop, two inner while loops and an if-else to determine
      * whether the users input is a palindrome.
      *
      * @param s The string input to be tested
      * @return true The users input is a palindrome
      * @return false The users input isn't a palindrome
      **/
    public static boolean isPalindrome(String s){
  
      int first, last;
  
      for(first = 0, last = s.length()-1 ; first &lt; last ; first++ , last-- ){
        while( (int)s.charAt(first) &lt; 'a' || (int)s.charAt(first) &gt; 'z' ){
          first++;
        }
        while( (int)s.charAt(last ) &lt; 'a' || (int)s.charAt(last ) &gt; 'z' ){
          last--;
        }
      }
      if( first &gt; last || s.charAt(first) != s.charAt(last) ){
        //return isPalindrome(s.substring(0, s.length()-1)) == false;
        return false;
      }
      else{
        //return isPalindrome(s.substring(0, s.length()-1)) == true;
        return true;
      }
    }
  
    /**
     * This method takes out punctuation marks in the string parsed
     * through, using Java's regular expressions (regex) and Java's
     * inbuilt method replaceAll(). The regex expression is passed
     * through the replaceAll() method to remove all non alpha-numeric
     * characters from the string passed through the method's parameter.
     * 
     * @param t The string that will have punctuation stripped from it.
     *
     * @return t The string has had all non alpha-numeric characters
     * removed and the new string is then returned.
     */
    public static String normalise(String t){
      t = t.replaceAll("[^a-zA-Z0-9]", "");
      return t;
    }
  
    /** removeSpaces(): A method that deletes spaces from the users input
      * and then decrements the string length count so any indexes aren't missed
      * when it is incremented.
      * 
      * @param s The string which is going to have it's spaces removed.
      * @return temp The new string is then returned after the spaces have been taken out.
      **/
    public static String removeSpaces(String s){
      StringBuilder temp = new StringBuilder(s); //creates a new StringBuilder with the inputted String
      for(int i = 0; i &lt; temp.length(); i++){ //do this for the entire length of the StringBuilder
  
        if(temp.charAt(i) == ' '){ //if the char at i is a space
  
          temp.deleteCharAt(i); //remove the char
          i--; //subtract 1 from the counter so we don't miss an index when we increment it
        }
      }
      return temp.toString(); //return the new String
    }
  }
  </code></pre>
  
  <hr>
  
  <p>I have blanked out the recursive statements in the recursive method for now. If someone can tell me what exactly I have done wrong and also help me in implementing a solution that would be really good. I would rather stick with the iterative version because I understand the mechanics of it, but have been asked to do a recursive version (I have been Java coding since after my mid year break last year but am a relative novice at recursion) which is proving to be quite a challenge. If you alter the code and it ends up working with the recursive version please explain how, when, why etc with your alterations. Am not looking for someone to just do this for me, I'm wanting to learn and it seems that I have learned best by example (I did get a B pass last year by analysing examples and reading explanations of implementations). Many thanks :).</p>
  
  <p>EDIT: I think I have got the recursion going ok now, just the logic is the thing confusing me at the moment. Here is the recoded version of the isPalindrome() method:</p>
  
  <pre><code>  public static boolean isPalindrome(String s){
  
      int first, last;
      boolean isPalindr = true;
  
      if (s.length() &lt;= 1){
        return true; // Base case
      }
  
      for(first = 0, last = s.length()-1 ; first &lt; last ; first++ , last-- ){
  //      while( (int)s.charAt(first) &lt; 'a' || (int)s.charAt(first) &gt; 'z' ){
  //        first++;
  //      }
  //      while( (int)s.charAt(last ) &lt; 'a' || (int)s.charAt(last ) &gt; 'z' ){
  //        last--;
  //      }
  //  }
        if( first == last || s.charAt(first) == s.charAt(last) ){
          //return isPalindrome(s.substring(first, last));
          return isPalindrome(s.substring(first, last)) == true;
          //isPalindr = false;
        }
        else{
          return isPalindrome(s.substring(first, last)) == false;
          //isPalindr = true;
        }
      }
      return isPalindr;
    }
  </code></pre>
  
  <p>If someone can help me with the logic I think this will be fixed :).</p>