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 Recursive number problem Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Recursive number problem" Watch "Recursive number problem" New topic
Author

Recursive number problem

Brandon Peeples
Ranch Hand

Joined: Jan 06, 2010
Posts: 38
Hello, I'm having trouble with a recursive number problem. Here is the problem:

Write a static method printRange that takes
integer parameters x and y and that prints the sequential integers between x
and y inclusive. The first half of the list should be printed with the greater-than
character (">") separating consecutive values. The second half should be
printed with the less-than character ("<") separating consecutive values. All
output should be on the current line of output.

printRange(1, 9);
System.out.println();
printRange(8, 20);
System.out.println();
printRange(-8, -8);
System.out.println();

should produce the following output:
1 > 2 > 3 > 4 > 5 < 6 < 7 < 8 < 9
8 > 9 > 10 > 11 > 12 > 13 > 14 < 15 < 16 < 17 < 18 < 19 < 20
-8

When there are two values in the middle of the range, those two values should
be separated by a dash. For example:

printRange(1, 10);
System.out.println();
printRange(13, 14);
System.out.println();

should produce the following output:
1 > 2 > 3 > 4 > 5 - 6 < 7 < 8 < 9 < 10
13 - 14


Here is what I have so far:



My code only works if x and y are equal, and if x is 1. I tried using a relationship between y-x to track the place a number is in, but I couldn't keep the value constant. I can't use any loops. The problem must be solved with recursion. I keep trying to get it to work without x starting from 1, but I'm having difficulty. Any advice or guidance is appreciated. Thank you.
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18117
    
  39



I am assuming that the goal of "temp" is to calculate the number, in between x and y. Question. Does this do that?

Henry


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

Joined: Jan 06, 2010
Posts: 38
That's correct Henry. It works well if the first parameter x starts with a 1. I tried to get it to work with any integer but having difficulty in doing so. It doesn't calculate the number between x and y. I tried to do something like (y-x)/2 but that didn't work out well since the value of x keeps increasing.
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18117
    
  39

Brandon Peeples wrote:I tried to do something like (y-x)/2 but that didn't work out well since the value of x keeps increasing.


What does "x keeps increasing" have to do with anything?

Henry
Jim Hoglund
Ranch Hand

Joined: Jan 09, 2008
Posts: 525
How about a different strategy. Using two StringBuilder objects
build the "<" half from the top number down to half the difference,
and the ">" part from the lower number up. Then concatenate the
two adding the "-" if necessary. Does this meet the requirements?
Jim...


BEE MBA PMP SCJP-6
Brandon Peeples
Ranch Hand

Joined: Jan 06, 2010
Posts: 38
I increase x when I make the recursive call. I was thinking that it wouldn't seem right because if I did subtract x from y, it would always give me a different value each time since x increases. I am definitely doing something wrong here. Thank you for your comments Henry. I know your trying to get me to think about the logic more.

That is an interesting idea Jim. Unfortunately, it doesn't meet the requirements. Thanks though
D Heller
Greenhorn

Joined: Feb 23, 2010
Posts: 2
Brandon Peeples wrote:I increase x when I make the recursive call. I was thinking that it wouldn't seem right because if I did subtract x from y, it would always give me a different value each time since x increases. I am definitely doing something wrong here. Thank you for your comments Henry. I know your trying to get me to think about the logic more.

That is an interesting idea Jim. Unfortunately, it doesn't meet the requirements. Thanks though


I think its also not right because the (x-y)/2 is not midway between x and y, its just the distance between the two numbers..

y/2 is actually only the "midpoint" when x = 0, in fact.. but (I believe.. if I am reading this right) your code is making it look like its correct for x = 1 because you add 1 to it
before you print it out..
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19543
    
  16

You get the center using the universal averaging code: (x_1 + x_2 + ... + x_n) / n. In this case, it's (x + y) / 2.

If x + y is even this will return you the exact center. If it doesn't it returns you 1/2 left of the center. To get the other side (1/2 right of it) simply add 1/2: (x + y + 1) /2. Now if x + y is even, then (x + y) / 2 and (x + y + 1) / 2 will both return the same value. Use that to your advantage.

SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6
How To Ask Questions How To Answer Questions
Brandon Peeples
Ranch Hand

Joined: Jan 06, 2010
Posts: 38


I think its also not right because the (x-y)/2 is not midway between x and y, its just the distance between the two numbers..

y/2 is actually only the "midpoint" when x = 0, in fact.. but (I believe.. if I am reading this right) your code is making it look like its correct for x = 1 because you add 1 to it
before you print it out..


I see what your saying. Thanks.

Brandon Peeples
Ranch Hand

Joined: Jan 06, 2010
Posts: 38
Rob Prime wrote:You get the center using the universal averaging code: (x_1 + x_2 + ... + x_n) / n. In this case, it's (x + y) / 2.

If x + y is even this will return you the exact center. If it doesn't it returns you 1/2 left of the center. To get the other side (1/2 right of it) simply add 1/2: (x + y + 1) /2. Now if x + y is even, then (x + y) / 2 and (x + y + 1) / 2 will both return the same value. Use that to your advantage.


Wow Rob... You are absolutely right. Thanks!
D Heller
Greenhorn

Joined: Feb 23, 2010
Posts: 2
Brandon Peeples wrote:I increase x when I make the recursive call. I was thinking that it wouldn't seem right because if I did subtract x from y, it would always give me a different value each time since x increases. I am definitely doing something wrong here. Thank you for your comments Henry. I know your trying to get me to think about the logic more.

That is an interesting idea Jim. Unfortunately, it doesn't meet the requirements. Thanks though


I think another issue here might be to rethink your strategy a bit.. I don't think x is really "increasing" when you make the call with parameters x+1 and y, if I were writing a recursive method like that I would try to make sure it gives the right output for all values of the parameters regardless of the "starting point" where I first called the method -- because otherwise its impossible to tell if the method is "correct" or not.. (at least as far as I can tell) -- since there are too many recursive possibilities for different function calls (i.e. again, it should work the same way each time its called with the same parameters, whether called recursively or not..)

hope that makes sense?
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18117
    
  39


Interesting note. For a recursive solution, you actually do not need to calculate the midpoint between x and y. You just need to handle the end conditions or otherwise setup for recursion.

The end conditions are... (1) if x > y (error), (2) if x = y, and (3) if x + 1 = y. And the recursive call is to increase x by 1 and decrease y by 1.

Henry
Brandon Peeples
Ranch Hand

Joined: Jan 06, 2010
Posts: 38
Henry Wong wrote:
Interesting note. For a recursive solution, you actually do not need to calculate the midpoint between x and y. You just need to handle the end conditions or otherwise setup for recursion.

The end conditions are... (1) if x > y (error), (2) if x = y, and (3) if x + 1 = y. And the recursive call is to increase x by 1 and decrease y by 1.

Henry


Thanks for the input guys. I'll give that a shot.
Brandon Peeples
Ranch Hand

Joined: Jan 06, 2010
Posts: 38
Everything seems to be working great now except for the part after the middle. How could I make the method stop at the last number in the list (2nd inputted parameter)? I can't get it to stop running infinitely or mess up the list of numbers.
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19543
    
  16

Can you show us your new method?
Brandon Peeples
Ranch Hand

Joined: Jan 06, 2010
Posts: 38

Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18117
    
  39


First, those end condition checks should return from method -- and not drop to the next check. After all, they are end conditions. It does seem okay, but just to be safe, in case you change something.

Anyway, you forget to print the y part of the recursive call -- which should be done after the recursive call returns.

Henry

Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19543
    
  16

Henry is right. If x + 1 == y, then x < y. Since only one of each conditions can be true, why not use if-else ifs?
Brandon Peeples
Ranch Hand

Joined: Jan 06, 2010
Posts: 38
Rob Prime wrote:Henry is right. If x + 1 == y, then x < y. Since only one of each conditions can be true, why not use if-else ifs?


That makes sense. The problem I'm having is how can I make it stop without being infinite. If x+1 == y... how do I set the limit.
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18117
    
  39

Brandon Peeples wrote:
That makes sense. The problem I'm having is how can I make it stop without being infinite. If x+1 == y... how do I set the limit.


Well, if you make sure that end conditions actually end, instead of falling into the next condition, and causing another recursive call, it won't be infinite. As suggested in the last hint...

Henry
Brandon Peeples
Ranch Hand

Joined: Jan 06, 2010
Posts: 38
Oh wow... it finally all makes sense now. I appreciate everyone's input. Thanks guys. Everything works now. I think a huge problem was that I didn't fully know how recursion worked. For instance, being able to print output after making a recursive call. I finally understand how recursion works. Thanks.

Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18117
    
  39

You can get rid of line 7 (the y++ line). It doesn't do anything.

Henry
Brandon Peeples
Ranch Hand

Joined: Jan 06, 2010
Posts: 38
You're right. Got it coach.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Recursive number problem
 
Similar Threads
What is the output?
how to compare the values in arrays
another 3 questions
two possible answers Q18 ch 4 page 282 from KB