Palindrome Recursion

[jk336699]

Hi everyone!
I'm new to programming and got really confused by the idea of recursion

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!

[sunde887]

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.

[Junky]

There is no recursion in this code.

Since the code is incomplete I imagine the assigment is for the OP to write it.

[jk336699]

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

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

[Junky]

Do you have a question?

[jk336699]

that's all... Thanks=)

[Junky]

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

Mind you recursion can turn you into a basket case.