Win a copy of Programmer's Guide to Java SE 8 Oracle Certified Associate (OCA) this week in the OCAJP forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

recursion....im an idiot!!

 
Justin Fox
Ranch Hand
Posts: 802
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
ok i have to write a program which takes a string from the user, then using a recursive function, return that string reversed.

here is what i have so far, i know that you have to have a "base"..



ok, we just started on recursion, and i'm not that good a thinking recursivly

i can do this with an interation loop, but i dont understand how you
would do this recursivly, because with a for loop you have to have two
variables one incrementing and one decrementing and just swaping every
interation...

please help,
Justin
[ April 06, 2006: Message edited by: Monk Fox ]
 
Ernest Friedman-Hill
author and iconoclast
Marshal
Pie
Posts: 24212
35
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,

OK, first thing: remember that the first character of a String is charAt(0), not charAt(1)!

OK, work with me here: if the String is one character long, then we return that character; that much you're already established. We want to return that one character as a String, though, of course, not a char. It would be convenient to just return the argument itself, yes?

Now, what if the String is two characters? Tell me what you would do, just for this one case. When we've got that straight, we'll move on.
 
Justin Fox
Ranch Hand
Posts: 802
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
ok sorry about the charAt(1) I was in a hurry, umm...

i know i should just do "return word;"

but if it is two characters long, lol, i have no idea how do do that recursivly.

i know all i have to do is get the program do switch only the first two

characters, then i call call the reverse function within itself to do it again, again, and again, up to the length of the string.

umm, lol I'm pretty much stumped.....sorry
 
Justin Fox
Ranch Hand
Posts: 802
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
the thing is though, i want to actually learn this stuff hardcore, and know it for datastructures.....

i dont want to just remember how someone else did it and just copy cat...

but it's pretty tough...

do i just use a loop to switch em once, then call the function after that

so it keeps on doing it?
 
Ernest Friedman-Hill
author and iconoclast
Marshal
Pie
Posts: 24212
35
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You didn't answer my question.

If you have a two character string, what should the function return?

It's an easy question. Work with me here!
 
Justin Fox
Ranch Hand
Posts: 802
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
ok if i have a two character string say.... "ab"

it should return "ba"

that should answer your question...
 
Ernest Friedman-Hill
author and iconoclast
Marshal
Pie
Posts: 24212
35
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Or in other words, it should return the last character of the String followed by the first character of the String, right?

So for 1 character, we return the last character of the String.

For two characters, we return the last character, followed by the first character.

Now, trying to use the same language, let's extend it to three characters. What do we do in this case?
 
Henry Wong
author
Marshal
Pie
Posts: 21393
84
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Monk Fox:

that should answer your question...


EFH was trying to get you think recursively with the question...

Let me try... Given any string, how would you reverse the string, if you are only allowed to pull the very first letter off. You are allow to build the string anyway you like.... but you are only allowed to pull the first letter off, and only once per method call.

Henry
[ April 06, 2006: Message edited by: Henry Wong ]
 
Layne Lund
Ranch Hand
Posts: 3061
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think one thing that is difficult about understanding recursion is that you have to write a function that is defined using itself. In otherwords, you have to assume that the function you are writing already works! I think the best way to help with this is to understand exactly what the function is supposed to do. In this case it seems clear, the function takes a String as a parameter and returns the String with all the characters in reversed order.

If you can get over this part, then you also need to figure out how to break down the input into smaller pieces that can then be solved by using the same function (that you are assuming works already). So in this example, how you can create a smaller String that you can reverse (this is the recursive part)? Then how do you put the pieces back together to return the result.

Hopefully this along with EFH's comments can help you start "thinking recursively".

Layne
 
Tony Morris
Ranch Hand
Posts: 1608
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Layne Lund:
I think one thing that is difficult about understanding recursion is that you have to write a function that is defined using itself. In otherwords, you have to assume that the function you are writing already works! I think the best way to help with this is to understand exactly what the function is supposed to do. In this case it seems clear, the function takes a String as a parameter and returns the String with all the characters in reversed order.

Layne


Agreed entirely. Another perspective is where there is a bidirectional dependency; A depends on B and B depends on A.
- A being the requirement of the function
- B being the recursive invocation of the function

One may struggle to analyse the symbiotic relationship between A and B to distinguish and conceptualise in finer detail. This simple case permits it relatively easy.
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic