Recursion

[Justin Fox]

here is my code

Main Class:

    
 
public class InovateImple
{
 
public static void main (String [] arg)
{
 
Inovate inovate = new Inovate();
 
String a = "hello";
 
System.out.println(a);
 
inovate.ReverseIt(a);
 
System.out.println(a);
 
}
}

Method Class:

    
 
public class Inovate
{
 
public String ReverseIt(String word)
 
{
char temp;
char [] array = new char [word.length()];
int I = 0, J = array.length - 1;
 
if (word.length() == 1)
return word;
 
for(int i = 0; i<word.length(); i ++)
{
 
array[i] = word.charAt(i);
}
 
if (I <= J)
{
temp = array[I];
array[I] = array[J];
array[J] = temp;
 
I ++;
J ++;
 
ReverseIt(word);
}
 

 
return word;
 
}
 
}
 
I'm getting all kinds of errors, I super lost on this whole recursion thing
 
someone please lead me in the right direction, thanks a lot...
 
justin

[Jesper de Jong]

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.

[Justin Fox]

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]

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.

[Justin Fox]

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]

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

[fred rosenberger]

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.

[Justin Fox]

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]

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]

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]

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]

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 ]

[Justin Fox]

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]

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]

This might be a little more help. Here is a link to a recursive factorial program

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

public class RecursiveFactorial
 
{
  public static void main( String [] args )
  {
    // compute factorial of 7 and output it
    System.out.println( "Factorial ( 7 ) is "
                      + factorial( 7 ) );
  }
 
  public static int factorial( int n )
  {
    if ( n <= 0 )  // base case
     return 1;
    else    // general case
     return ( n * factorial ( n - 1 ) );
  }
}

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]

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]

reverse(hello) = o + reverse(hell)

[Rusty Shackleford]

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]

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!!