C++ Palindromes

A palindrome is a string that reads the same forwards and backwards. A strict palindrome includes spaces; in an ordinary palindrome we ignore spaces. Letter case is irrelevant and punctuation is ignored. A palindromic number is composed of only numbers. Able was I, ere saw Elba A man, a plan, a canal: Panama! 2445442 a strict palindrome an ordinary palindrome a decimal palindromic number Write a recursive algorithm to determine whether or not a string is (or is not) a palin- drome: Base Case: General Case: string length is if first letter !- last letter, false, otherwise remove first and last letter and call the method again Recall that C++ strings are arrays of type char C++ strings are NUL terminated; the array is traversed until NUL is encountered C++ we get to play with pointers! So if we determine that the first and last letters of our string are the same we can over- write the last char in the string with NUL and then make the recursive call with the argu- ment // address of the "second" char in &thestring[1] the string This is destructive, so if we do it this way we must make a copy of the original string and send the copy to our recursive function. This means that our algorithm has linear spatial performance (on the string length); we need only two copies of the string. If we do it the Java way (make copies of substrings) our spatial performance is quadratic on the string ength