11 Replies - 694 Views - Last Post: 22 October 2013 - 12:41 PM Rate Topic: -----

#1 streek405  Icon User is offline

  • D.I.C Addict

Reputation: 12
  • View blog
  • Posts: 606
  • Joined: 10-March 13

Reversing an arrray using recursion

Posted 05 October 2013 - 08:19 PM

Can someone please tell my why my else statement is not working properly

 // the driver 
      public void reverse(){
         reverse(0, length - 1);
      }
   	
   // reverse this String182
      public void reverse(int LF, int RT) {
      	
			//this array will hold the reversed order
         char[] newArray = new char[length];
      //the easiest case
         if(LF > RT){
         }
         
         else if(LF == RT){
            letters[LF] = letters[RT];
				System.out.print(letters[LF]);
         }
			
			
         else{
			
         	//reverse the order
         	newArray[LF] = letters[RT]; 
				System.out.print(newArray[LF]);
				reverse(LF + 1 , RT - 1);
				
         }      
      }



When I run this, and lets say the array is orginally "Computers", the output is only "sretu". Why? I tried writing this down on paper, to help me see this better, and, in this case, when it reaches the forth index, LF will have the same index value of RT
so something like this:
INDEXS REVERSING
0 = 8
1 = 7
2 = 6
3 = 5
4 = 4
5 = 3
6 = 2
7 = 1
8 = 0
Do they lose their values after the 4th index for some reason? OR is it my IF/ ELSE IF statement screwing things up?

This post has been edited by streek405: 05 October 2013 - 08:24 PM


Is This A Good Question/Topic? 0
  • +

Replies To: Reversing an arrray using recursion

#2 jon.kiparsky  Icon User is offline

  • Pancakes!
  • member icon


Reputation: 7996
  • View blog
  • Posts: 13,694
  • Joined: 19-March 11

Re: Reversing an arrray using recursion

Posted 05 October 2013 - 08:51 PM

Examine your recursive cases and ask yourself, when do you set the value of some index >N/2? In this case, is there ever a situation where LF equals, say, 6, and anything happens?

(there are simpler recursive algorithms for this, but I think the one you're chasing should work, so keep at it... you can learn the other ones after you've made yours work, that's good practice for you)

This post has been edited by jon.kiparsky: 05 October 2013 - 08:51 PM

Was This Post Helpful? 1
  • +
  • -

#3 streek405  Icon User is offline

  • D.I.C Addict

Reputation: 12
  • View blog
  • Posts: 606
  • Joined: 10-March 13

Re: Reversing an arrray using recursion

Posted 06 October 2013 - 10:45 PM

View Postjon.kiparsky, on 05 October 2013 - 08:51 PM, said:

Examine your recursive cases and ask yourself, when do you set the value of some index >N/2? In this case, is there ever a situation where LF equals, say, 6, and anything happens?

I would do that after the 5th index? I think I see what you are trying to say, that when i > n/2 it should copy the index value of n/2 - 1. So something like this maybe?

	else if(LF > length/2){
				
				newArray[LF] = letters[RT];
				System.out.prin(newArray[LF]);
				reverse(LF + 1, RT - 1);
			}

But wouldnt that conflict with my IF statement? As for your 2nd statement, no because my IF statement will ruin it...darn. Hmmm...I cant take out my IF statement cuz then if there is a 0 size array it will go into my ELSE and get a run time error maybe.

Quote

(there are simpler recursive algorithms for this, but I think the one you're chasing should work, so keep at it... you can learn the other ones after you've made yours work, that's good practice for you)

lol I noticed that I tend to over complicate things when I write code. I remember for one of my methods, a while back, all I needed was 2 lines of code only to make the entire thing work, yet I used something like 10-15 lines :(
Was This Post Helpful? 0
  • +
  • -

#4 streek405  Icon User is offline

  • D.I.C Addict

Reputation: 12
  • View blog
  • Posts: 606
  • Joined: 10-March 13

Re: Reversing an arrray using recursion

Posted 06 October 2013 - 10:55 PM

jon.kiparsky, here is my updated code, however I am not that content with it. it works, but it seems to me that I have overcomplicated it, mainly with the ELSE IF and ELSE.

public void reverse(int LF, int RT) {
      	
			//this array will hold the reversed order
         char[] newArray = new char[length];
      //the easiest case
		
         if(length == 0){
         }
         
         // else if(LF == RT){
//             letters[LF] = letters[RT];
// 				System.out.print(letters[LF]);
//          }
			else if(LF >= length/2){
				if(RT >= 0){
				newArray[LF] = letters[RT];
				System.out.print(newArray[LF]);
				reverse(LF + 1, RT - 1);
				}
			}
			
         else{
				if(RT >= 0){
         	//reverse the order
         	newArray[LF] = letters[RT]; 
				System.out.print(newArray[LF]);
				reverse(LF + 1 , RT - 1); 
				}
         }      
      }


do you think this can be better or is this not that bad?

This post has been edited by streek405: 06 October 2013 - 11:46 PM

Was This Post Helpful? 0
  • +
  • -

#5 jon.kiparsky  Icon User is offline

  • Pancakes!
  • member icon


Reputation: 7996
  • View blog
  • Posts: 13,694
  • Joined: 19-March 11

Re: Reversing an arrray using recursion

Posted 07 October 2013 - 12:05 AM

Yes, this is a little more complex than it needs to be. Consider whether you can reduce your non-base cases to one case. Either we're done, or we have to do some work. There is no decision to be made about what the work to be done is.

EDIT:
Think about it in terms of teamwork. We're going to reverse this array. I'm going to hand you everything but the first and the last items, and trust you to return to me a reversed version of what I handed you. What is left for me to do so that when I'm done, I have a completely reversed array?

This post has been edited by jon.kiparsky: 07 October 2013 - 12:11 AM

Was This Post Helpful? 0
  • +
  • -

#6 streek405  Icon User is offline

  • D.I.C Addict

Reputation: 12
  • View blog
  • Posts: 606
  • Joined: 10-March 13

Re: Reversing an arrray using recursion

Posted 07 October 2013 - 12:39 AM

View Postjon.kiparsky, on 07 October 2013 - 12:05 AM, said:

Yes, this is a little more complex than it needs to be. Consider whether you can reduce your non-base cases to one case.


So, it's possible for me to combine my ELSE IF and ELSE into into one thing?

Quote

EDIT:
Think about it in terms of teamwork. We're going to reverse this array. I'm going to hand you everything but the first and the last items, and trust you to return to me a reversed version of what I handed you. What is left for me to do so that when I'm done, I have a completely reversed array?

Forgive me, but is this a hypothetical question? If so, then is your 2nd statement something like this: you have the numbers 1 - 10, you are going to give me numbers 2 - 9, and now I need to reverse it? If so, then would I do something like:
public void reverse(int frontEnd, int backEnd){
   
   int[] array = new int[oldArray.length];

   if(frontEnd > backEnd){}
   
   else if(frontEnd == backEnd){
      System.out.println(array[frontEnd]);
   }
   //my guess
   else{
      array[frontEnd] = array[backEnd];
      reverse(frontEnd + 1, backEnd - 1);     
   }
}

//the driver
public void reverse(){
   reverse(1, length -2); //since i do not have the first and last values?
}



**EDIT Actually, this would all be the same this as my previous code, but the driver would be different, right?

This post has been edited by streek405: 07 October 2013 - 12:40 AM

Was This Post Helpful? 0
  • +
  • -

#7 jon.kiparsky  Icon User is offline

  • Pancakes!
  • member icon


Reputation: 7996
  • View blog
  • Posts: 13,694
  • Joined: 19-March 11

Re: Reversing an arrray using recursion

Posted 07 October 2013 - 12:46 AM

No, let's just assume that what you give back is going to be reversed. We can even imagine that you have a magic array-reversing wand, if that helps. I just know that you're going to do your part, but I'm responsible for dealing with 1 and 10, getting those in the right place. What do I have to do?

(Don't make this complicated - if you think this is a very simple question, you're on the right track)

To be specific: I get [1,2,3,4,5,6,7,8,9,10], and I give you [2,3,4,5,6,7,8,9]. I trust you to give me [9,8,7,6,5,4,3,2]. I have to deal with 1 and 10. What do I do?

This post has been edited by jon.kiparsky: 07 October 2013 - 12:48 AM

Was This Post Helpful? 0
  • +
  • -

#8 streek405  Icon User is offline

  • D.I.C Addict

Reputation: 12
  • View blog
  • Posts: 606
  • Joined: 10-March 13

Re: Reversing an arrray using recursion

Posted 07 October 2013 - 09:12 AM

View Postjon.kiparsky, on 07 October 2013 - 12:46 AM, said:

To be specific: I get [1,2,3,4,5,6,7,8,9,10], and I give you [2,3,4,5,6,7,8,9]. I trust you to give me [9,8,7,6,5,4,3,2]. I have to deal with 1 and 10. What do I do?

For your part, you would subtract the arrays total length by 2 and make that the new arrays length, and then transfer the values to a new array, starting from i[1] to i[length -2].
Was This Post Helpful? 0
  • +
  • -

#9 jon.kiparsky  Icon User is offline

  • Pancakes!
  • member icon


Reputation: 7996
  • View blog
  • Posts: 13,694
  • Joined: 19-March 11

Re: Reversing an arrray using recursion

Posted 07 October 2013 - 11:38 AM

No, no. I don't touch anything in the subarray. If you want, we can both have the same array, and I'm just passing you the start and end points of the part that you're in charge of. (this is in fact how it's usually going to be done)

Think simpler. I hand you the subarray, and get it back in reversed order. (thank you). That's just a method call, no work to do on my end. Then I take the element at the front and the element at the back, and I swap them, and now the array is reversed.


So think about that for a little bit, and then imagine that you get a clever idea. Instead of doing any work yourself, you're just going to hand me the subarray that I handed to you. What happens then? Well, obviously I now have an array to reverse, so I just hand you the subarray consisting of everything but the first and last elements, and I ask you to sort it. And while I'm waiting around for you to come back with that subarray in reversed order, someone knocks on my door and says "oh, here's an array for you to reverse". So I do the same thing, and .... some repetitions later, I'm handed an array of length zero. Well, even I know how to do that: just give it back. So I do. And then you just hand it back to me as a return value, and I put the first and last elements back on it, in swapped order, and return that to you. And of course I immediately get that value back as a return, and so forth, until I finally have reassembled the array in reversed order and I give it back to whoever wanted it in the first place.

And that's how this recusion works.

This is a cute story, and I hope it helps you visualize the correct way of thinking about recursive calls, but there's one important detail that I've got wrong, because I can't really get it right in the story. That detail is that the "me" that is doing all of this work is actually a clone of me. That clone has no idea that any other copy of itself exists, and it doesn't know about any other process, and it can never know about those things. This actually helps a lot, because it means that the clone can never get confused about which first and last elements go with which subarrays. It only knows about the single subarray problem it was created to deal with.
Was This Post Helpful? 1
  • +
  • -

#10 streek405  Icon User is offline

  • D.I.C Addict

Reputation: 12
  • View blog
  • Posts: 606
  • Joined: 10-March 13

Re: Reversing an arrray using recursion

Posted 07 October 2013 - 08:22 PM

View Postjon.kiparsky, on 07 October 2013 - 11:38 AM, said:

Think simpler. I hand you the subarray, and get it back in reversed order. (thank you). That's just a method call, no work to do on my end. Then I take the element at the front and the element at the back, and I swap them, and now the array is reversed.

OHHH!!!! i get what you're saying now! took me long enough...ok that makes sense

Quote

So think about that for a little bit, and then imagine that you get a clever idea. Instead of doing any work yourself, you're just going to hand me the subarray that I handed to you. What happens then? Well, obviously I now have an array to reverse, so I just hand you the subarray consisting of everything but the first and last elements, and I ask you to sort it. And while I'm waiting around for you to come back with that subarray in reversed order, someone knocks on my door and says "oh, here's an array for you to reverse". So I do the same thing, and .... some repetitions later, I'm handed an array of length zero.

its cuz you would keep taking off the front and last values over and over, right?

Quote

This is a cute story,
cuter than Twilight :')

So, pretty much recursion will call itself over and over with different values: either inc/dec to reach a limit or by cutting it in half over and over.
Was This Post Helpful? 0
  • +
  • -

#11 jon.kiparsky  Icon User is offline

  • Pancakes!
  • member icon


Reputation: 7996
  • View blog
  • Posts: 13,694
  • Joined: 19-March 11

Re: Reversing an arrray using recursion

Posted 07 October 2013 - 08:34 PM

Quote

its cuz you would keep taking off the front and last values over and over, right?


Yes - and a different front and last value each time. So each time, I get a smaller subproblem, which is what we want with a recursive call.

Quote

So, pretty much recursion will call itself over and over with different values: either inc/dec to reach a limit or by cutting it in half over and over.


Yes, this is what we mean by "simplifying a problem towards a base case"
Was This Post Helpful? 0
  • +
  • -

#12 streek405  Icon User is offline

  • D.I.C Addict

Reputation: 12
  • View blog
  • Posts: 606
  • Joined: 10-March 13

Re: Reversing an arrray using recursion

Posted 22 October 2013 - 12:41 PM

View Postjon.kiparsky, on 07 October 2013 - 08:34 PM, said:



I know this post is old, but I really wanted to thank you for your example and story! My professor was re-explaining recursion again and how it work and I thought of your little story. He pretty much said the same thing, stating that the first recursive call is going to wait for the 2nd recursive call to finish, while the 2nd recursive call waits for the 3rd recursive call to finish and etc.

So THANKS! :D/>
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1