permaculture playing cards*
The moose likes Beginning Java and the fly likes Recursion Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of The Java EE 7 Tutorial Volume 1 or Volume 2 this week in the Java EE forum
or jQuery UI in Action in the JavaScript forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Recursion" Watch "Recursion" New topic
Author

Recursion

Justin Fox
Ranch Hand

Joined: Jan 24, 2006
Posts: 802
here is my code

Main Class:


Method Class:



You down with OOP? Yeah you know me!
Jesper de Jong
Java Cowboy
Saloon Keeper

Joined: Aug 16, 2005
Posts: 14114
    
  16

Your question is vague. What does "all kinds of errors" mean exactly? Look at the errors one by one, try to understand what they mean and solve them.

Don't panic if you get a whole bunch of errors, just take it one (small) step at a time.


Java Beginners FAQ - JavaRanch SCJP FAQ - The Java Tutorial - Java SE 7 API documentation
Scala Notes - My blog about Scala
Justin Fox
Ranch Hand

Joined: Jan 24, 2006
Posts: 802
well the errors are crazy .... big time...


at java.lang.ClassLoader.defineClass1(Native Method)
at java.lang.ClassLoader.defineClass(Unknown Source)
at java.security.SecureClassLoader.defineClass(Unknown Source)
at java.net.URLClassLoader.defineClass(Unknown Source)
at java.net.URLClassLoader.access$100(Unknown Source)
at java.net.URLClassLoader$1.run(Unknown Source)
at java.security.AccessController.doPrivileged(Native Method)
at java.net.URLClassLoader.findClass(Unknown Source)
at java.lang.ClassLoader.loadClass(Unknown Source)
at sun.misc.Launcher$AppClassLoader.loadClass(Unknown Source)
at java.lang.ClassLoader.loadClass(Unknown Source)
at java.lang.ClassLoader.loadClassInternal(Unknown Source)

lol thats all of em...and the one in main is ...java.lang.NoDefFound

or something like that

Help me!!!

justin
Joanne Neal
Rancher

Joined: Aug 05, 2005
Posts: 3477
    
  13
Those aren't errors as such. They are a stack trace which gives information about where the error occurred. Cut and paste the whole of the output as there is usually a lot of useful information in a stack trace.


Joanne
Justin Fox
Ranch Hand

Joined: Jan 24, 2006
Posts: 802
ok, seriously, i have a problem right?.... well i just saw that i

incremented J instead of decrementing it, which probably threw an out of

bounds exception....

ok, at first i put the ReverseIt(word) out of the if(I<=J) statement, but

just kept calling itself until the program terminated...

then i put the ReverseIt(word), inside of the if(I<+J) statement thinking,

maybe that if i have limitations on I and J that the function will on call

itself as long as I is in fact, <= J.

now if my assuming this is wrong, please tell me how i might go about

making my program work.

like i know what a stack trace is?....im on chaper 11 in my college book

right now, which is recusion....stacks are in chapter 12, and its breif. I

dont learn more about that subject until datastructures....

i know ya'll like to talk all distinguished and everything, but i need

help, not a vocabulary lesson....

now, please answer my question..

justin
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18753
    
  40

now, please answer my question..


Sorry if you already know this... but "recursion" is an algorithm (or "technique" if you prefer). It is not an API which you just use.

In your case, you can't just have the ReverseIt() method call itself with the same parameters -- and expect only to do some magic setup prior to that, to get it to work.

You must understand what you are doing. In this regard, I suggest you go back to pen and paper, and design what you want your method to do. Taking care of end conditions, and working out scenarios. etc.

Henry


Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11249
    
  16

there is a difference between a "stack trace", and the stack data structure.

cutting and pasting just part of the error message is not helpful. or rather, the part that you showed us is not the (most) helpful part.

people here DO want to help, but you have to make it easy for us to do so. You may want to read this if you haven't yet.

So, please post the ENTIRE error message.


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Justin Fox
Ranch Hand

Joined: Jan 24, 2006
Posts: 802
sorry to have confused you, making you think i believe in magic...

i thought that if i used

if (I<= J)
{
blah
blah
blah
}

that the if statement would keep doing ReverseIt(word), until it got

to the middle, then stop, and return the word..

but all it does is keep saying....


at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)
at Inovate.ReverseIt(Inovate.java:29)

and i cant see whats before the at....

i figured, once I and J equaled each other the if statement would stop.

and then return the word..
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18753
    
  40


i thought that if i used

if (I<= J)
{
blah
blah
blah
}

that the if statement would keep doing ReverseIt(word), until it got

to the middle, then stop, and return the word..

but all it does is keep saying....


This is what is happening...

- Allocate a new array, along with I = 0, and J = array length minus one
- return if string is size one -- let's assume it is not size one
- copy the string characters to the newly allocated string array
- check if I<=J, which is true because I = 0 and J = array length minus one
- exchange the first and last character of the newly allocated array
- increment both I and J
- recusively call itself with the original string that was passed, which...

- Allocate another new array, and another I = 0, and J = length - 1;
- return if string is size one -- which should still not be one.
- copy the string characters to the newly allocated string array
- check if I<=J, which is true because I = 0 and J = array length minus one
- exchange the first and last character of the newly allocated array
- increment both I and J
- recusively call itself with the original string that was passed, which...

- Allocate another new array, and another I = 0, and J = length - 1;
- return if string is size one -- which should still not be one.
- copy the string characters to the newly allocated string array
- check if I<=J, which is true because I = 0 and J = array length minus one
- exchange the first and last character of the newly allocated array
- increment both I and J
- recusively call itself with the original string that was passed, which...

- Allocate another new array, and another I = 0, and J = length - 1;
- return if string is size one -- which should still not be one.
- copy the string characters to the newly allocated string array
- check if I<=J, which is true because I = 0 and J = array length minus one
- exchange the first and last character of the newly allocated array
- increment both I and J
- recusively call itself with the original string that was passed, which...

...
blah
blah
blah
...

This should keep going until you run out of memory.

Henry
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18753
    
  40

i figured, once I and J equaled each other the if statement would stop.

and then return the word..


Basically, you are allocating a new array, a new I, and a new J with each recursive call.

You do exchange the letters in your array, but you don't pass that array to the next call. Nor the I or the J to the next call.


If you can figure out how to get your method to work with the same array, I, and J ...

Henry
Justin Fox
Ranch Hand

Joined: Jan 24, 2006
Posts: 802
ok, so i need to do another for loop to create the word that i just made,

then ReverseIt(new word) until the I==j?

i tried for(int i = 0; i<array.length;i++)
{
word.charAt(i) = "array[i]";
}
Rusty Shackleford
Ranch Hand

Joined: Jan 03, 2006
Posts: 490
You usually do not need to put loops into a recursive method. All you need to do is work through the string, recursively until you get to element n/2, where n initially was equal to String.length-1. This implies that each recursive call you need to pass the string, n-1 and m+1, where m is the index in the first half of the string.

First, I would suggest that you write this out iteratively to make sure you that you understand how to reverse a string(or array). There are a few sublties that can trip you up. Most prominent is swapping elements n-1 to 0, which has the end effect of doing nothing. but being very inefficient at it.

After you got that working. You can switch to the recursive solution. The iterative will tell you what goes where. First you need your exit condition, and then figure out what to pass to itself.

The suggestion to write it out of paper is an excellent one. Follow along on paper what is happening on the stack each call.
[ April 13, 2006: Message edited by: Rusty Shackleford ]

"Computer science is no more about computers than astronomy is about telescopes" - Edsger Dijkstra
Justin Fox
Ranch Hand

Joined: Jan 24, 2006
Posts: 802
I dont understand this stuff one bit...

doing this in iteration is easy, ive done it before...

but i dont understand how do do this with a recursive method..

i know i need two variables....one for the index of word and one for the

length...

i dont see how you can keep up dating the variables though, when you have

to keep calling the function over again...

it just starts over again and again and again...


iteration

for (int i = 0; int j = word.length()-1;i<j;i++;j--)
{
char temp = word.charAt(i);
word.charAt(i) = word.charAt(j);
word.charAt(j) = temp;
}
return word;

iteration is simple....recursion is rediculous....

i need help understanding the recursive thought..

but it makes no sense...
Rusty Shackleford
Ranch Hand

Joined: Jan 03, 2006
Posts: 490
ask yourself:

If a method I am about to call needs two current variables, one incremented, one decremented, how do I pass them?

The answer is quite simple, and is the same answer for a recursive method.

Hint: think about ++ and -- operators.

When you call any method, recursive or not, everything in that method is created from 'scratch' and doesn't know anything about any other method data, including other recursive methods of the same name currently on the stack. Also, each recursive step should do one step generally. In this case, each call should check to see if the exit condition has been reached, if not perform one swap, then call itself. So the next call needs the String of course, plus the next index values for the next swap. Rinse and repeat.

When the exit condition has been reached, it is a mater of passing the String back through all the previous called methods, so make sure the method has 2 return statement. One in the if statement, and one as the last line in the method.

If this is for a school assignment, I strongly suggest taking advantage of the instructors office hours.
[ April 13, 2006: Message edited by: Rusty Shackleford ]
Rusty Shackleford
Ranch Hand

Joined: Jan 03, 2006
Posts: 490
This might be a little more help. Here is a link to a recursive factorial program

http://www.hostitwise.com/java/java_recursion.html



If you don't know factorial is simply 1*2*3*...*n. The program starts from n and works backward.

Run it if you like, but don't pass a very high value or you will exceed the range on an int. Probably 11! or 12!. Or you can use it to trace on paper.

Hopefully this will help your understanding without doing your work for you.

Disclaimer: I did not run this code, so I can't guarentee it is correct, although glancing at it, it does look right.
Justin Fox
Ranch Hand

Joined: Jan 24, 2006
Posts: 802
i think i've got it....

ok say i have the string "hello" to reverse right?

ok...if i return the o

then just repass the substring of hello, hell, then return the l

then repass the substring of hell, hel, then return the l

then repass the substring of hel, he, then return the e

the repass the substring of he, h, then return the h

the whole time concatinating what i return together....

then return the end string, that should work right?
Garrett Rowe
Ranch Hand

Joined: Jan 17, 2006
Posts: 1296
reverse(hello) = o + reverse(hell)


Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter
Rusty Shackleford
Ranch Hand

Joined: Jan 03, 2006
Posts: 490
Yeah, that just might work. Try it out.

BTW, some of my comments were more toward reversing an array, rather then a immutable String. Sorry if that gave you any confusions. Although you could make good use of charAt() and replace()
Justin Fox
Ranch Hand

Joined: Jan 24, 2006
Posts: 802
its cool, im just glad i finally trully understand it....

yeah i figured that out....

return string.substring(string.length()) + reverse(string.substring(0,

string.length()-1);

and i would just make my base:

if (string.length() == 0)
return string;

i did do 1, but it wouldn't of returned the h...so i did 0

dont know if it works yet, but im perdy sure it will.....

thanks for helping me out...

once again this site has proven to be the best!!
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Recursion