AP Computer Science Exam Question

Consider the following problem:

A palindrome is a word, phrase, number, or other sequence of characters that reads the same forward and backward. Write a recursive function is_palindrome that takes a string as input and returns true if the string is a palindrome, and false otherwise. The function should not be case-sensitive, meaning that uppercase and lowercase letters should be considered equal.

You may assume that the input string will only contain alphanumeric characters and spaces.

public class RecursiveThinking {
    public static boolean is_palindrome(String str) {
        // Base case: an empty string or string with only one character is a palindrome
        if (str.length() == 0 || str.length() == 1) {
            return true;
        }
        
        // Recursive case: check if the first and last characters of the string are equal
        char firstChar = Character.toLowerCase(str.charAt(0));
        char lastChar = Character.toLowerCase(str.charAt(str.length() - 1));
        
        if (firstChar != lastChar) {
            return false;
        }
        
        // Recursively call is_palindrome with the substring between the first and last characters
        return is_palindrome(str.substring(1, str.length() - 1));
    }
}

Explain how the is_palindrome function works using the given sample code.

Answer:

The is_palindrome function is a recursive function that checks whether a given string is a palindrome or not. It follows the following steps:

1. Check the base cases: If the string has a length of 0 or 1, it is considered a palindrome (since it reads the same forwards and backwards), so the function returns true.

2. For strings with a length greater than 1, we proceed to the recursive case:

3. Retrieve the first and last characters of the string. To make the function case-insensitive, we convert both characters to lowercase using the Character.toLowerCase() method.

4. Compare the first and last characters. If they are not equal, it means the string is not a palindrome, so the function returns false.

5. If the first and last characters are equal, we proceed with the recursive step. We call the is_palindrome function with the substring obtained by removing the first and last characters from the original string.

6. The function continues to recursively call itself with the smaller substring until it reaches a base case or finds a pair of non-matching characters.

7. If the recursive calls successfully reach a base case without returning false, the function concludes that the original string is a palindrome and returns true.

The recursive nature of the function allows it to repeatedly check pairs of characters from the beginning and end of the string, gradually reducing the size of the problem until it reaches a base case or determines that the string is not a palindrome.