Palindrome Program using Recursion

Question

This is currently what I have for my Palindrome program for my computer science class. I have it pretty much working, except whenever a word is a palindrome, it is an infinite loop. I know I have to insert a number base case, but I do not how to do that...I'm really having trouble understanding recursion. Help is appreciated.

public class PalindromeTester
{
    public static void main(String[] args)
    {
        Scanner scan = new Scanner (System.in);

        String str, another = "y";
        int left, right;

        while (another.equalsIgnoreCase("y"))
        {

            System.out.println("Enter a potential palindrome:");
            str = scan.next();

            left = 0;
            right = str.length() - 1;

            tester(str, left, right);

            System.out.println();
            System.out.println("Test another palindrome (y/n)?");
            another = scan.next();

        }
    }

    public static void tester (String str, int left, int right)
    {
        Scanner scan = new Scanner (System.in);


        while (str.charAt(left) == str.charAt(right) && left < right)
        {
            System.out.println(str);

            tester( str, left + 1, right -1);

        }
        if (left < right)
        {
            System.out.println("That string is NOT a palindrome.");
        }

        else 
        {

            System.out.println("That string IS a palindrome.");
        }

    }
}

Read [Check string for palindrome](http://stackoverflow.com/questions/4138827/check-string-for-palindrome) — Braj, Apr 06 '14 at 16:16
Your while loop is never ending because you don't change left and right in the loop. Either use a loop, or use recursion but don't try to use both. — Vincent van der Weele, Apr 06 '14 at 16:20

score 1 · Answer 1 · answered Apr 06 '14 at 16:44

You are using a while loop. With recursion, this is done implicitly.

You have to split the algorithm in small parts.

[] represents left, {} represents right.

[1] 2 3 4 5 6 7 8 9 0 9 8 7 6 5 4 3 2 {1} -->Level 0
1 [2] 3 4 5 6 7 8 9 0 9 8 7 6 5 4 3 {2} 1 -->Level 1
1 2 [3] 4 5 6 7 8 9 0 9 8 7 6 5 4 {3} 2 1 -->Level 2
1 2 3 [4] 5 6 7 8 9 0 9 8 7 6 5 {4} 3 2 1 -->Level 3
1 2 3 4 [5] 6 7 8 9 0 9 8 7 6 {5} 4 3 2 1 -->Level 4
1 2 3 4 5 [6] 7 8 9 0 9 8 7 {6} 5 4 3 2 1 -->Level 5
1 2 3 4 5 6 [7] 8 9 0 9 8 {7} 6 5 4 3 2 1 -->Level 6
1 2 3 4 5 6 7 [8] 9 0 9 {8} 7 6 5 4 3 2 1 -->Level 7
1 2 3 4 5 6 7 8 [9] 0 {9} 8 7 6 5 4 3 2 1 -->Level 8
1 2 3 4 5 6 7 8 9 {[0]} 9 8 7 6 5 4 3 2 1 -->Level 9

So, tester will continue until:

We've reached the middle of the word.
The word is not a palindrome

Example of case 2:

[1] 2 3 A 5 6 7 8 9 0 9 8 7 6 5 4 3 2 {1} 
1 [2] 3 A 5 6 7 8 9 0 9 8 7 6 5 4 3 {2} 1 
1 2 [3] A 5 6 7 8 9 0 9 8 7 6 5 4 {3} 2 1 
1 2 3 [A] 5 6 7 8 9 0 9 8 7 6 5 {4} 3 2 1 --> !!!

I thought this method would be very helpful for the understanding of how is this recursion working

public static String positions(String word, int l, int r) {
        char[] a = word.toCharArray();
        String s = "";
        // [letter] if left, {} if right, [{}] if both 
        for (int i = 0; i < a.length; i++) {
            if (l == i && r == i) {
                s += "{[" + a[i] + "]}";
            } else if (l == i) {
                s += "[" + a[i] + "]";
            } else if (r == i) {
                s += "{" + a[i] + "}";
            } else {
                s += a[i];
            }
            s+=" ";
        }
        return s;

    }

And finally, the tester method.

public static boolean tester(String str, int left, int right) {

        System.out.println(positions(str, left, right) +" tester(str, "+left +", "+right+")");
        if (left>=right) // case 1
            return true; // that's ok, we've reached the middle
            // the middle was not reached yet.
            // is the condition satisfied?
        if (str.charAt(left) == str.charAt(right)) {
            // yes. So, lets do it again, with the parameters changed
            return tester(str, left + 1, right - 1);

        } 
        //the condition was not satisfied. Let's get out of here.
        else {

            return false;
        }

    }

Some outputs:

Enter a potential palindrome:
1234567890987654321
[1] 2 3 4 5 6 7 8 9 0 9 8 7 6 5 4 3 2 {1}  tester(str, 0, 18)
1 [2] 3 4 5 6 7 8 9 0 9 8 7 6 5 4 3 {2} 1  tester(str, 1, 17)
1 2 [3] 4 5 6 7 8 9 0 9 8 7 6 5 4 {3} 2 1  tester(str, 2, 16)
1 2 3 [4] 5 6 7 8 9 0 9 8 7 6 5 {4} 3 2 1  tester(str, 3, 15)
1 2 3 4 [5] 6 7 8 9 0 9 8 7 6 {5} 4 3 2 1  tester(str, 4, 14)
1 2 3 4 5 [6] 7 8 9 0 9 8 7 {6} 5 4 3 2 1  tester(str, 5, 13)
1 2 3 4 5 6 [7] 8 9 0 9 8 {7} 6 5 4 3 2 1  tester(str, 6, 12)
1 2 3 4 5 6 7 [8] 9 0 9 {8} 7 6 5 4 3 2 1  tester(str, 7, 11)
1 2 3 4 5 6 7 8 [9] 0 {9} 8 7 6 5 4 3 2 1  tester(str, 8, 10)
1 2 3 4 5 6 7 8 9 {[0]} 9 8 7 6 5 4 3 2 1  tester(str, 9, 9)
true

Test another palindrome (y/n)?
y
Enter a potential palindrome:
12345A678654321
[1] 2 3 4 5 A 6 7 8 6 5 4 3 2 {1}  tester(str, 0, 14)
1 [2] 3 4 5 A 6 7 8 6 5 4 3 {2} 1  tester(str, 1, 13)
1 2 [3] 4 5 A 6 7 8 6 5 4 {3} 2 1  tester(str, 2, 12)
1 2 3 [4] 5 A 6 7 8 6 5 {4} 3 2 1  tester(str, 3, 11)
1 2 3 4 [5] A 6 7 8 6 {5} 4 3 2 1  tester(str, 4, 10)
1 2 3 4 5 [A] 6 7 8 {6} 5 4 3 2 1  tester(str, 5, 9)
false

Test another palindrome (y/n)?

In the main method,

System.out.println(tester(str, left, right));

In order to see the true/false output

score 0 · Answer 2 · answered Apr 06 '14 at 16:16

Since your are using recursion (in its basic purposes mostly used to eliminate loops), isn't your while loop inside the tester() method supposed to be an if?

public static void tester (String str, int left, int right)
{
    Scanner scan = new Scanner (System.in);

    if (str.charAt(left) == str.charAt(right) && left < right)
    {
        System.out.println(str);

        tester( str, left + 1, right -1);

    }
    else if (left < right)
    {
        System.out.println("That string is NOT a palindrome.");
    }

    else 
    {
        System.out.println("That string IS a palindrome.");
    }
}

score -1 · Answer 3 · answered Apr 06 '14 at 16:18

I modified your tester() method and replaced your while with an if and moved your second if clause.

public static void tester(String str, int left, int right) {
        if (str.charAt(left) == str.charAt(right) && left < right) {
            tester(str, left + 1, right - 1);
        } else {
            if (left < right) {
                System.out.println("That string is NOT a palindrome.");
            } else {
                System.out.println("That string IS a palindrome.");
            }
        }
    }

Palindrome Program using Recursion

3 Answers3