Sign in to follow this  

quick recursion question

This topic is 3567 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

so yeah, I'm usually good with doing recursion, but this particular java situation has got me puzzled. Basically what I'm trying to do is whatever string I'm given, i want to return a "cleaned" string where adjacent chars that are the same have been reduced to a single char. so basically "yyzzza" would be converted to "yza". the function i have constructed is: public String stringClean(String str){ } so basically, if there is adjacent multiples of any letter, its reduced to one letter in the string. Does anyone particularly have an idea what i should do?

Share this post


Link to post
Share on other sites
i know you guys would think that buts not, im practing java on my own by doing the javabat's and this is one of the problems. i know the rules...

Share this post


Link to post
Share on other sites
Quote:
Does anyone particularly have an idea what i should do?
Yep.



But it would help if you show what you've tried, and why your solutions didn't work.

Quote:
Thats where I'm kinda stuck


One hint is to realize that the characters will only move backwards, or stay in same spot. So the new string will be of same size or smaller, and no character will ever move forward.

Share this post


Link to post
Share on other sites
Recursion can be (ab)used to simulate any(?) loop, so if you can write a loop without recursion that does this, it should be relatively straightforward to convert it into a recursive function.

For example, the infamous factorial function has a 1:1 conversion to a standard loop.


int FactorialLoop(int number)
{
int temp = 1;

while (number > 1)
{
temp *= number;
number = number - 1;
}

return temp;
}

int FactorialRecursion(int number)
{
if (number > 1)
return number * FactorialRecursion(number - 1);

return 1;
}


Both cases have the same concepts:

1. A repeating section of code.
2. A "number" variable which is being decremented.
3. A temporary value being accumulated (the return value in the recursion).
4. A specific exit condition.

[Edited by - Nypyren on March 7, 2008 9:10:43 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Antheus
One hint is to realize that the characters will only move backwards, or stay in same spot. So the new string will be of same size or smaller, and no character will ever move forward.


I haven't used Java, but I've heard that C# is very similar to Java. Are strings in Java immutable like they are in C#?

If they are, then there won't be any "moving" of characters ;)

Share this post


Link to post
Share on other sites
Quote:
Original post by Nypyren
Quote:
Original post by Antheus
One hint is to realize that the characters will only move backwards, or stay in same spot. So the new string will be of same size or smaller, and no character will ever move forward.


I haven't used Java, but I've heard that C# is very similar to Java. Are strings in Java immutable like they are in C#?


Yes, they are.

Quote:
If they are, then there won't be any "moving" of characters ;)


Using standard library's string it's not possible to develop in-place version of algorithm. That's true for recursive or iterative variant.

All, in-place and out-of-place, recursive or iterative variants perform same number of character copies, but out-of-place requires an extra allocation for target string.

Share this post


Link to post
Share on other sites
let rec unique = function
| a::b::t -> if a = b then unique (a::t) else a::unique (b::t)
| x -> x
;;


You only need to translate list-based operations into string_based operations, and you'll be set.

Share this post


Link to post
Share on other sites

This topic is 3567 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this