• Post Reply Bookmark Topic Watch Topic
  • New Topic

recursion  RSS feed

 
Dana Horst
Ranch Hand
Posts: 38
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello guys!
here is the task i have to solve:
Given a string, compute recursively a new string where all the adjacent chars are now separated by a "*".

allStar("hello") → "h*e*l*l*o"
allStar("abc") → "a*b*c"
allStar("ab") → "a*b"

Here is my solution,which is not completed:



Please correct the code so it produces string witj * between every elements. Thank you!
 
Jesper de Jong
Java Cowboy
Sheriff
Posts: 16057
88
Android IntelliJ IDE Java Scala Spring
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Do you understand why your code doesn't do what it's supposed to do?

To understand why, think about what happens in line 10. Specifically: suppose that str contains "hello", what happens in line 10 in that case?

Note that line 12 will never be reached. In lines 4 and 6 you checked for a string with length 0 or 1, so the condition in line 9 (length of the string is greater than 1) is always true.
 
Dana Horst
Ranch Hand
Posts: 38
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks for reply Jesper. With putting conditions with length() == 0 || 1 i try to evoid error if String will be empty or with length 1. With line 10 I have a difficulty - dont know how to formulate the rule correct.
 
Jesper de Jong
Java Cowboy
Sheriff
Posts: 16057
88
Android IntelliJ IDE Java Scala Spring
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Simply try to imagine what happens when the program runs.

Suppose that you call allStar("hello");. What happens?

The length of "hello" is 5, so the conditions in lines 4 and 6 are false. It gets to line 9. The length of "hello" is greater than 1, so it's going to execute line 10.

In line 10, you call allStar again, and the input is going to be the original string "hello", with a "*" appended to it. So, you're calling allStar("hello*");.

It starts the method from the top (a recursive call), but now, str contains "hello*".
It gets to line 10 again, where it's going to call allStar again, with the original string "hello*" with a "*" appended to it. So, you're calling allStar("hello**");.

It starts the method from the top (a recursive call), but now, str contains "hello**".
It gets to line 10 again, where it's going to call allStar again, with the original string "hello**" with a "*" appended to it. So, you're calling allStar("hello***");.

It starts the method from the top (a recursive call), but now, str contains "hello***".
It gets to line 10 again, where it's going to call allStar again, with the original string "hello**" with a "*" appended to it. So, you're calling allStar("hello***");.

It starts the method from the top (a recursive call), but now, str contains "hello***".
It gets to line 10 again, where it's going to call allStar again, with the original string "hello***" with a "*" appended to it. So, you're calling allStar("hello****");.

It starts the method from the top (a recursive call), but now, str contains "hello****".
It gets to line 10 again, where it's going to call allStar again, with the original string "hello****" with a "*" appended to it. So, you're calling allStar("hello*****");.

...

It starts the method from the top (a recursive call), but now, str contains "hello***********************".
It gets to line 10 again, where it's going to call allStar again, with the original string "hello***********************" with a "*" appended to it. So, you're calling allStar("hello************************");.

Etcetera, until the string becomes to large that you get an OutOfMemoryError or the stack becomes so deep that you get a StackOverflowError.

Re-think the logic, especially what should happen in line 10.
 
Stuart A. Burkett
Ranch Hand
Posts: 679
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
In order for a recursive call to finish you need to reach your end condition (the condition where you don't recursively call the method). Your end condition is that the length of your parameter string is zero or one.
However, every time you call the method you are making the string longer (by appending * to it), so your end condition will never be reached. You need to be recursively calling the method with a substring of the string that was passed in.
 
Dana Horst
Ranch Hand
Posts: 38
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you both for the answers!
 
Tyson Lindner
Ranch Hand
Posts: 211
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If its not specifically required by the assignment, just use a loop that adds to an empty string. Recursion isn't needed at all here.
 
Kumar Krishna
Greenhorn
Posts: 1
Eclipse IDE Firefox Browser Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Moderator action: Ready-made solution removed.
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Kumar Krishna wrote:

Kumar,

First: Welcome to JavaRanch.

Second: I'm not quite sure if your code was meant to be a solution or not, but if it was, please be advised: we are NotACodeMill (←click).
I'm sure your intentions were great, but we don't like people to simply hand out solutions, particularly in the "Beginning Java" section.

I have removed the code from your post. If you would like to re-post with something that helps Dana to find his own solution, please feel free.

Winston
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!