• Post Reply Bookmark Topic Watch Topic
  • New Topic

Reverse Sentence  RSS feed

 
Daniel Smith
Greenhorn
Posts: 6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello,
I need help writting a recursive program that reverses a sentence.
Example,
Input: Hello World
Output: World Hello
I have no clue how to write this program or where to begin.
Thanks for all your help,
Daniel
[ March 29, 2004: Message edited by: Daniel LastNameTaken ]
 
Tim West
Ranch Hand
Posts: 539
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This sounds strangely like an assignment question ;-)
Well, with recursion, you first need to define what you're recursing on. Suppose you have a sentence defined as an array of words, W[n] being the nth word, from 0 to n-1. (To match Java arrays). You're going to be recursing somehow on the length of W.
Then, let recurse(W, a, b) be the problem of recursing sentence W between words a and b.
You then need to define two things:
1. The termination condition (ie, when do we stop recursing?)
2. The "action" of recursion - that is, defining recurse(W, a, b) in terms of a smaller problem of itself. Think about what happens if you swap the first and last words, and then what you have to do in the middle.
This is all fairly theoretical, but I'm not too keen to write out the program for you. Have a go and post any problems you have back up here, we're all happy to help.
Cheers,

--Tim
 
Carlos Failde
Ranch Hand
Posts: 84
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Recursion!? Bah! Want you need is iteration:

Erm, but seriously, good luck with that assignment.
 
Daniel Smith
Greenhorn
Posts: 6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks for your help. This is for an assignment but not for me for a friend.
 
Dirk Schreckmann
Sheriff
Posts: 7023
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Daniel LastNameTaken,
Welcome to JavaRanch!
We ain't got many rules 'round these parts, but we do got one. Please change your display name to comply with The JavaRanch Naming Policy.
Note that your display name doesn't have to match your login name.
Thanks Pardner! Hope to see you 'round the Ranch!
 
Dirk Schreckmann
Sheriff
Posts: 7023
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This is for an assignment but not for me for a friend.
Perhaps your friend would do well to be doing the work and asking the questions.
 
Daniel Smith
Greenhorn
Posts: 6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello, this is what I got for my recursive function. But for some reason it only works when you have two words. Once you have a sentence with more then two word in it the output is crazy. Any reason why?
Thanks for your help,
Daniel
 
Mike Gershman
Ranch Hand
Posts: 1272
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Several points:
1. I cut and pasted your code and it works fine.
2. Therefore, the problem is in your driver that calls Recursion and prints the results.
3. If a<b then a!=b, so your your code has an extra conditional.
4. While I wrote a simple driver to test your code, I didn't give it to you. I just told you where to look for the bug. That's how you should help your friend. Are you going to take your friend's exams too?
 
Ben Buchli
Ranch Hand
Posts: 83
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
it doesnt work for more than 2 words because your method can only handle 2.
you got to write a loop in your method so that it works for a whole sentence with more than 2 words, or use recursion.
however, your recursion method is not a recursion. a recursion uses the output from calculation 1 for calculating the next output and so forth, hope that makes sense.
 
Mike Gershman
Ranch Hand
Posts: 1272
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Ben:
Algorithms like Quicksort use the kind of recursion Daniel did, recursing on the indices but manipulating a shared array.
I tested Daniel's exact code and it worked fine. His code calls itself with indices a and b pointing to the two words next closer to the middle of the phrase. You could do the same thing with a loop, but the assignment called for recursion.
Did you test the code? Where is the bug?
Mike
 
Dirk Schreckmann
Sheriff
Posts: 7023
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Daniel,
Please edit your display name to include a last name.
 
Ben Wood
Ranch Hand
Posts: 342
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
How about

 
Carlos Failde
Ranch Hand
Posts: 84
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Ben Wood:
How about


Output: ecnetnes ym si sihT
Ooh so close!
 
Ben Wood
Ranch Hand
Posts: 342
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
doh!
 
Ben Wood
Ranch Hand
Posts: 342
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
ta da!

[ March 31, 2004: Message edited by: Ben Wood ]
 
chi Lin
Ranch Hand
Posts: 348
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Daniel,
The implementation indeed reverse the sentence, you just find
a right place to output/return the result.
my approach/hint : add a line after the if clause.

 
Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
See if this recursive algorithm makes sense:

I'd break out the first word and the rest of the line with a simple indexOf(" ") to find a blank, then take the stuff before and after the blank. Be sure to trim the parts so multiple blanks don't mess you up.
BTW: Iteration would be a better solution in real life, but if recursion is the assignment, recursion it better be!
 
Daniel Smith
Greenhorn
Posts: 6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The bug was located at the place were I call the function. Thanks you for helping.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!