Results 1 to 7 of 7
  1. #1
    jk336699 is offline Member
    Join Date
    Aug 2011
    Posts
    3
    Rep Power
    0

    Default Palindrome Recursion

    Hi everyone!
    I'm new to programming and got really confused by the idea of recursion
    Java Code:
    public class Palindrome {
    
        // Internal state of object
        Scanner in;                // Stream where we look for palindromes
        int min;                   // Minimum length we look for
        boolean buffered = false;  // Do we have the next palindrome already in the buffer?
        String buffer = "";        // Buffer to hold the next palindrome
    
    
        /**
        * Main program.
        *     Invoke as "java Palindrome 5 wordlist.txt" to test words in wordlist.txt
        */
        public static void main(String [] args)
        throws FileNotFoundException
            {
            String fileName = null;
            int minLength = 0;
            if (args.length != 2) {
                System.err.println("Usage: java Palindrome len file\n");
                System.exit(1);
            }
            minLength = Integer.parseInt(args[0]);
            fileName = args[1];
    
            Scanner in = new Scanner( new File( fileName ) );
            Palindrome palFinder = new Palindrome( in, minLength );
            //palFinder.runTests(); // Comment this out in final version
            while (palFinder.hasNextPalindrome()) {
                String palindrome = palFinder.getNextPalindrome();
                System.out.println(palindrome);
            }
        }
    
    
        /**
        * Construct a palindrome finder.
        * @param scanner  A scanner on a stream of candidate palindrome words
        * @param minLength The minimum length palindrome we will look for
        */
        public Palindrome( Scanner scanner, int minLength ) {
            this.in = scanner;
            this.min = minLength;
        }
    .
    .
    .
    }
    Why are there a main and a Palindrome method?
    and
    when it creates the Palindrome object, does java have to run through the stuff in the main?

    Thanks in advance!
    This is my first post and if i do anything wrong here let me know!

  2. #2
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    11

    Default

    There is only one methods(main), the palindrome "method" is actually a constructor. Constructors are necessary to create an instance of an object. There is no recursion in this code. Recursion deals with applying a method repeatedly on smaller versions of the input. Did you write this code yourself? I ask this because if you wrote it yourself you would more easily understand what is happening. If not, no worries. Here is some material I believe will be helpful:

    The Really Big Index - Use this for anything you don't fully understand

    http://www.java-forums.org/blogs/sun...recursion.html - a blog post about recursion.

  3. #3
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,807
    Rep Power
    10

    Default

    Quote Originally Posted by sunde887 View Post
    There is no recursion in this code.
    Since the code is incomplete I imagine the assigment is for the OP to write it.

  4. #4
    jk336699 is offline Member
    Join Date
    Aug 2011
    Posts
    3
    Rep Power
    0

    Default

    Thanks a lot sunde887
    I think i understand now

    I didnt write the code by myself
    it was found under class assignment folder
    I think where to apply recursion is under the isPalindrome method

    Java Code:
    /**
    * Palindrome finder.
    * @author Your name here
    */
    import java.util.Scanner;
    import java.io.File;
    import java.io.FileNotFoundException;
    
    public class Palindrome {
    
        // Internal state of object
        Scanner in;                // Stream where we look for palindromes
        int min;                   // Minimum length we look for
        boolean buffered = false;  // Do we have the next palindrome already in the buffer?
        String buffer = "";        // Buffer to hold the next palindrome
    
    
        /**
        * Main program.
        *     Invoke as "java Palindrome 5 wordlist.txt" to test words in wordlist.txt
        */
        public static void main(String [] args)
        throws FileNotFoundException
            {
            String fileName = null;
            int minLength = 0;
            if (args.length != 2) {
                System.err.println("Usage: java Palindrome len file\n");
                System.exit(1);
            }
            minLength = Integer.parseInt(args[0]);
            fileName = args[1];
    
            Scanner in = new Scanner( new File( fileName ) );
            Palindrome palFinder = new Palindrome( in, minLength );
            //palFinder.runTests(); // Comment this out in final version
            while (palFinder.hasNextPalindrome()) {
                String palindrome = palFinder.getNextPalindrome();
                System.out.println(palindrome);
            }
        }
    
    
        /**
        * Construct a palindrome finder.
        * @param scanner  A scanner on a stream of candidate palindrome words
        * @param minLength The minimum length palindrome we will look for
        */
        public Palindrome( Scanner scanner, int minLength ) {
            this.in = scanner;
            this.min = minLength;
        }
    
        /**
        * Determine whether there is at least one more palindrome of
        * the required length in the  input stream.
        * @return true if there is at least one more palindrome in the input
        *  stream with length at least the minimum specified length.
        */
        public boolean hasNextPalindrome() {
            // FIX ME <- fixed
            // Consider the following cases:
            //    * There is already a palindrome in the buffer
            //    * The buffer has been emptied by getNextPalindrome(),
            //      so I need to search the input for one.
            while (in.hasNext()) {
                String candidate = in.next();
                if (candidate.length() >= min && isPalindrome(candidate)) {
                    buffer = candidate;
                    buffered = true;
                    return true;
                }
            }
            return false;
        }
    
        /**
        * Return the next palindrome of at least the specified length
        * from the input stream
        *     (assuming there is one - use hasNextPalindrome() to make sure)
        *
        * @return the next sufficiently long palindrome from the input stream
        */
        public String getNextPalindrome() {
            // The normal case is to call getNextPalindrome right after hasNextPalindrome
            if (! buffered && ! hasNextPalindrome()) {
                return null;
            }
            buffered = false;
            return buffer;
        }
        /**
        * Determine whether s is a palindrome.
        * @param s  string to be checked
        * @return true if and only if s is a palindrome
        */
        boolean isPalindrome( String s ) {
            // Recursive version starts with fingers on first and last letter
            return isPalindrome( s, 0, s.length() - 1);
        }
    
        /**
        * Recursive check of palindrome property for s[left]..s[right].
        * @param s string to be checked (from position left to position right)
        * @param left "left finger" - checking palindrome property starting here
        * @param right "right finger" - checking palindrome property to here
        */
        boolean isPalindrome( String s, int left, int right) {
            // FIX ME
            // Induction based on the length of the substring from
            // the left finger to the right finger
            // BASIS CASE:  left finger and right finger are together
            //              or the left finger has crossed over the right
            if (left == right || left > right){
    			return true;
       		}
            // BASIS CASE:  if letters under fingers don't match, must
            //        not be a palindrome
            if (s.charAt(left) != s.charAt(right)){
    			return false;
    		}
            // PROGRESS CASE: if the letters under the fingers match,
            //    the the word is palindromic if the remainder of the
            //    of the word (moving fingers inward) is a palindrome
            return isPalindrome(s, left+1, right-1);
        }
    
        // ***********************************************
        //   TEST DRIVER for the palindrome check method
        // ***********************************************
    
        /**
        * Run a palindrome test and report result.
        * @param s A string to be tested for palindrome property
        * @param expected True or False depending n whether s is a palindrome
        */
        void runPalindromeTest(String s, boolean expected) {
            boolean actual = isPalindrome(s);
            if (actual == expected) {
                System.out.println("(OK) tested string '" + s + "' => " + actual );
            } else {
                System.out.println("FAILED TEST on '" + s + "'");
                System.out.println("Expected " + expected + ", got " + actual);
            }
        }
    
        /**
        * Run my whole suite of test cases on checking whether a string
        * is a palindrome.
        */
        void runTests( ) {
            runPalindromeTest("", true);
            runPalindromeTest("a", true);
            runPalindromeTest("xx", true);
            runPalindromeTest("Xx", false);
            runPalindromeTest("abba", true);
            runPalindromeTest("aba", true);
            runPalindromeTest("abca", false);
            runPalindromeTest("abc", false);
        }
    }

  5. #5
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,807
    Rep Power
    10

    Default

    Do you have a question?

  6. #6
    jk336699 is offline Member
    Join Date
    Aug 2011
    Posts
    3
    Rep Power
    0

    Default

    that's all... Thanks=)

  7. #7
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,807
    Rep Power
    10

    Default

    By the way it is "base case" not "basis case".

    Mind you recursion can turn you into a basket case.

Similar Threads

  1. Palindrome
    By leepikamukharji in forum New To Java
    Replies: 2
    Last Post: 04-29-2011, 03:20 PM
  2. Palindrome program
    By trinity in forum New To Java
    Replies: 4
    Last Post: 04-16-2011, 03:22 AM
  3. Palindrome
    By pinkdreammsss in forum Java Applets
    Replies: 8
    Last Post: 05-04-2010, 03:59 PM
  4. recursion and tail-recursion differences
    By OptimusPrime in forum New To Java
    Replies: 2
    Last Post: 12-28-2009, 07:26 PM
  5. HELP...Palindrome
    By d7o0om in forum New To Java
    Replies: 12
    Last Post: 11-13-2009, 04:32 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •