Recursion question.?

Question

Basically I have an assignment to check weather a string is a palindrome, like dad, is a palindrome or not. The problem is I'm required to use recursion. I'm actually a bit confused on this one, if a recursive function is just a function that solves a problem by reducing it to smaller version of itself, then does that mean I can't use any form of a loop here? I thought of the following algorithm.

1) Get c-string
2) Use modulus to determine if indexSize is even or not
3) Use for loop to compare front index to back index...eg first and last
4)increase first counter, decrease second counter...
5)if index was an odd number…then if statement within the loop would compare middle index to middle index then break.


but that would involve irritation...

so I’m not really sure I’m getting the point...

any advice would be greatly appeared.

Oh and please do not post code solving my problem, I do the work and take the class to understand how to become a better programmer.

I code in multiple languages but this assignment is to be done in C++

Answer 1

Good policy there in your last sentence.

Here's what I would do: Ultimately, your base case is you run out of characters to compare, which is true if either there are no characters left to compare to each other or there is one character left. So first check for that. If either of these conditions are true, return true.

For the rest of the function, there are two or more characters to compare, you need to compare the first to the last. If they are the same, strip off this first and last and pass the remaining string to this function again. If they aren't the same, return false.

Good luck. Which language are you using?

BTW, Mr. idefix's solution does not seem to be recursive.

Answer 2

Here goes, in pseudocode.

Build your function to only compare the first and last characters of a string >=2. If string <2 return True. If firstchar and lastchar are not equal return False. If firstchar and lastchar are equal call your function (recurse) using a substring that omits firstchar and lastchar. Return the result of calling the function.

Got it? I leave it to you to figure out the details behind firstchar, lastchar, substring, etc.

Have fun. Enjoy your weekend.

Answer 3

I would try to split the string in characters and rewrite it starting from the last character and compare the 2 variables :

the first variable would hold the original string
the second one would hold the string spelt from right to left
So that if the 2 variables were equal then it would be a palindrome