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
    8

    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,798
    Rep Power
    7

    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,798
    Rep Power
    7

    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,798
    Rep Power
    7

    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, 04:20 PM
  2. Palindrome program
    By trinity in forum New To Java
    Replies: 4
    Last Post: 04-16-2011, 04:22 AM
  3. Palindrome
    By pinkdreammsss in forum Java Applets
    Replies: 8
    Last Post: 05-04-2010, 04: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
  •