[Recursion]

Question:

A student has written the following code. It is written to check whether a string is palindrome or not. However, the code is not giving the desired result when the parameter “MADAM” is passed to the method isPalindrome(). Analyse the code and find out the logical error.

public class PalindromeTesting
{
public static boolean isPalindrome(String word)
{
if(word.length()

Question

[Recursion]

Question:


A student has written the following code. It is written to check whether a string is palindrome or not. However, the code is not giving the desired result when the parameter “MADAM” is passed to the method isPalindrome(). Analyse the code and find out the logical error.



public class PalindromeTesting
{
    public static boolean isPalindrome(String word)
    {
        if(word.length() < 1)
        {
            return true;
        }

        else if(word.charAt(0) != word.charAt(word.length() - 1))
        {
            return false;
        }

        else
        {
            return isPalindrome(word.substring(0, word.length() - 1));
        }
    }
}

Accepted Answer

Answer:

Logical Error:


The recursive call:



return isPalindrome(word.substring(0, word.length() - 1));



is incorrect.



It removes only the last character of the string but does not remove the first character.



For palindrome checking, both the first and last characters should be removed after comparison.




Correct Statement:


return isPalindrome(word.substring(1, word.length() - 1));




Explanation:


Palindrome logic works as follows:



    Compare first and last characters
    If they are same, remove both characters
    Recursively check the remaining string



Example for:



"MADAM"



Correct recursive working:



MADAM
→ ADA
→ D
→ true



But in the given code:



MADAM
→ MADA
→ MAD
→ MA
→ M



The first character is never removed properly.



Therefore, the recursion logic becomes incorrect.




Corrected Method:


public static boolean isPalindrome(String word)
{
    if(word.length() < 1)
    {
        return true;
    }

    else if(word.charAt(0) != word.charAt(word.length() - 1))
    {
        return false;
    }

    else
    {
        return isPalindrome(word.substring(1, word.length() - 1));
    }
}




Conclusion:



    
        The logical error is in the recursive substring statement.
    

    
        Both first and last characters must be removed during recursion.
    

    
        Correct recursive call:
        
substring(1, word.length() - 1)

Answer with Explanation