Consider palindromes that consist only of lowercase letters

Consider palindromes that consist only of lowercase letters, such as \"level\" and \"deed,\" but not \"RadaR,\" \"ADA,\" or \"101.\" Let c(n) be the number of palindromes of length n.

Write a recursive definition of c(n).

Solution

A palindrome is a word that is spelled the same forward and backward. For example, as you stated \"level\" and \"deed\" are palindromes. but \"computer\" is not a palindrome.

Now consider the word \'a\' it is palindrome, In fact we don\'t have to think of palindomes as sctual words in the english language.

We can think of a palindrome as just any sequence of letters that reads the same forward and backward, such as xzyxyxyzx and so on with many combinations.

For instance any string containing just one letter is a palindrome. More over an empty string is also a palindrome because it reads the same from both forward and backward directions.

If the String is made of no letters or just one letter, then declare it as a palindrome.

Otherwise the first and last letters are the same. Strip them from the string, and determine whether the string that remains is a palindrome.

The Recursive Definition can be as follows:

palindrome (s[], first, last)

if s[first] == s[last] and s[first] == \'a\' or \'b\'
if first == last
This string is in the language
else
So far this string is in the language
palindrome (s[], first+1, last-1)
else
This string is not in the language