Win a copy of Mesos in Action this week in the Cloud/Virtualizaton forum!

# Recursive number problem

Brandon Peeples
Ranch Hand
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
Marshal
Posts: 21117
78

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

Henry

Brandon Peeples
Ranch Hand
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
Marshal
Posts: 21117
78
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
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...

Brandon Peeples
Ranch Hand
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
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
Posts: 20527
54
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.

Brandon Peeples
Ranch Hand
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
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
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
Marshal
Posts: 21117
78

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
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
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
Posts: 20527
54
Can you show us your new method?

Brandon Peeples
Ranch Hand
Posts: 38

Henry Wong
author
Marshal
Posts: 21117
78

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
Posts: 20527
54
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
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
Marshal
Posts: 21117
78
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
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
Marshal
Posts: 21117
78
You can get rid of line 7 (the y++ line). It doesn't do anything.

Henry

Brandon Peeples
Ranch Hand
Posts: 38
You're right. Got it coach.