🔒 Locked

quick recursion question

Started by baddogj Mar 7, 2008 at 8:48 PM 10 replies 2k views

Original Post

Mar 7, 2008 at 8:48 PM

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?

Nypyren

1,001

Nypyren

Mar 7, 2008 at 8:55 PM

This sounds suspiciously like homework, which the forum has a policy against.

The problem is simple enough that we can't give legitimate hints without giving the complete answer.

osmanb

Mar 7, 2008 at 8:56 PM

... smells like homework. Which is probably why you need (or think you need) to use recursion.

baddogj

Author

baddogj

Mar 7, 2008 at 9:00 PM

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...

Nypyren

1,001

Nypyren

Mar 7, 2008 at 9:03 PM

Do you HAVE to use recursion? It seems like it would be much easier as a linear pass.

baddogj

Author

baddogj

Mar 7, 2008 at 9:06 PM

Yeah it would be easier but part of the problem is to use recursion and no loops. Thats where I'm kinda stuck.

Antheus

216

Antheus

Mar 7, 2008 at 9:07 PM

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.

Nypyren

1,001

Nypyren

Mar 7, 2008 at 9:10 PM

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]

Nypyren

1,001

Nypyren

Mar 7, 2008 at 9:28 PM

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 ;)

baddogj

Author

baddogj

Mar 7, 2008 at 9:31 PM

never mind, i figured it out, but thanks for the help

Antheus

216

Antheus

Mar 7, 2008 at 9:39 PM

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.

ToohrVyk

238

ToohrVyk

Mar 8, 2008 at 3:32 AM

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.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.