Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

vkeller

Palidrome Recursion ?

This topic is 6924 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Does anyone know how to do a palidrome using recursion with c++. I do not undstand recursion.. I understand its usually only used in a classroom and not for real programming

Share this post


Link to post
Share on other sites
Advertisement

Give more info about your problem. Are you to tell wether or not a string is a palindrome, or are you to create a palindrome of some length?

Share this post


Link to post
Share on other sites
1) Do you want to only detect if a string is a palidrome?

2) Who ever told you recursion is only used in the classroom, and not in real programming is just plain wrong. Somethings are just better when done using recursion. Making a BSP tree from a list of polygons is just one.

Domini

Share this post


Link to post
Share on other sites
Well, first of all, there are lots of uses for recursion outside the classroom. Some problems are much easier to solve with a recursive solution (certain types of sorting, for example).

Recursion is when a function calls itself. Every recursive function needs to have a base case. That is, there needs to be some point where the recursion ends and the function returns.

As far as your problem goes, I''m not sure what you mean. If you are trying to CREATE a palindrome using a recursive algorithm, the pseudocode might be something like this:


palindrome(integer n)
{
if(n == 0)
return;
pick a number or letter and store it in variable X
print X
palindrome(n-1)
print X
}


In this case, n would be HALF the length of the palindrome you want to create. If you need a recursive function that determines whether or not a specific string is a palindrome, it is a bit trickier.

Maybe something like this would work?

bool is_palindrome(string s)
{
if( s.length < 2 )
return true;
if(s.first_character == s.last_character)
return is_palindrome(s.middle);
else
return false
}


Sorry for the pseudocode. Most of the pseudo functions should be self explanatory, but the s.middle function would return the original string missing the first and last characters.

Hopefully, I didn''t make too many mistakes and this will be helpful to you.

Share this post


Link to post
Share on other sites
ape-Sorry for being vague with my question. I wanted to check whether or not a string is a palindrome.
Domini - thanks for letting me know that recursion is used in the real world... wish I could remember where I read it its not.
jaxson- your pseudocode was helpful, I now see how the palindrome function calls itself.


Share this post


Link to post
Share on other sites
Hi -

To determine if a string is a palindrome, you can use the recursive descent algorithm to parse the string.

First you need a grammar such as:

A -> aAa / bAb / ...

Where A is a function that recursively checks the last and first sections of your string.

I hope that helps.

Emagen

Share this post


Link to post
Share on other sites
Yeah. A good example for recursion is for a factorial type function that figures out a factorial. I dont have the functions in front of me, but ive seen it and its pretty tight. Trailing though trees is a good application of recursion also.

Share this post


Link to post
Share on other sites
Recursion is used in the *real* world. It may not be the most common problem solving technique, but it is definately worth learning and understanding. A common place of use is in trees.


Mike

Share this post


Link to post
Share on other sites
If speed is a consern you would have to make sure that all of that pushing to and poping from the stack isn''t slower that just a plain ol'' loop. Or worse yet, it is sooo recursive that you actually exaust that stack.

Share this post


Link to post
Share on other sites
Sorry if this sounds really stupid, like I''ve missed something, but why use recursion to find if a string is a palindrome?

I would just make a reversed copy (ie last char first... etc) and do a string compare. This just sounds a bit quicker/more efficient than a bejillion function calls passing a string (its probably not, though, for the simple reason that it makes me look like a dickhead ).

-------------
squirrels are a remarkable source of protein...

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!