File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Beginning Java and the fly likes recursion....im an idiot!! Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "recursion....im an idiot!!" Watch "recursion....im an idiot!!" New topic
Author

recursion....im an idiot!!

Justin Fox
Ranch Hand

Joined: Jan 24, 2006
Posts: 802
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 ]

You down with OOP? Yeah you know me!
Ernest Friedman-Hill
author and iconoclast
Marshal

Joined: Jul 08, 2003
Posts: 24187
    
  34

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.


[Jess in Action][AskingGoodQuestions]
Justin Fox
Ranch Hand

Joined: Jan 24, 2006
Posts: 802
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

Joined: Jan 24, 2006
Posts: 802
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

Joined: Jul 08, 2003
Posts: 24187
    
  34

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

Joined: Jan 24, 2006
Posts: 802
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

Joined: Jul 08, 2003
Posts: 24187
    
  34

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
Sheriff

Joined: Sep 28, 2004
Posts: 19002
    
  40

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 ]

Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
Layne Lund
Ranch Hand

Joined: Dec 06, 2001
Posts: 3061
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


Java API Documentation
The Java Tutorial
Tony Morris
Ranch Hand

Joined: Sep 24, 2003
Posts: 1608
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.


Tony Morris
Java Q&A (FAQ, Trivia)
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: recursion....im an idiot!!