help with recursive function to print number patterns
I'm sorry for having to ask for homework help - I'm badly stuck on this! Can someone give me a kick in the right direction with this?
-
need a recursive function with a single positive int parameter n. the function should write (2^n - 1) integers and should be in the following pattern...
n = 1, Output: 1
n = 2, Output: 1 2 1
n = 3, Output: 1 2 1 3 1 2 1
n = 4, Output: 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
n = 5, Output: 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
function should valid for all positive integer values of n
-
This was tagged as a 'short' problem...so it shouldnt take too much code...I am hung on on the following:
*Do I keep track of the numbers printed, if so how? I only have a single parameter to call with so I am confused as to how I could get an entire pattern without keeping track of the history
*I had initially thought it would be necessary to cut it in half and do the 2nd half backwards (ie: for n=3, I would take care of the 1 2 1 - then 3 - then 1 2 1...but even then it seems like I could cut 1 2 1 in half the same way and therefor I should be able to do ALL of it in single parts...
Can someone veer me in the right direction here? I'm really lost with this.
[1297 byte] By [
Devina] at [2007-11-26 20:21:56]
> This was tagged as a 'short' problem...so it shouldnt
> take too much code...
Yeah, the method body could be done in a few lines.
> I am hung on on the following:
> *Do I keep track of the numbers printed, if so how?
Not explicitly. Use the call stack. That is, use the fact that when you're recursing, the previous values of numbers are preserved in the previous method invocation.
> I only have a single parameter to call with so I am
> confused as to how I could get an entire pattern
> without keeping track of the history
You don't have to store anything across method invocations.
> I had initially thought it would be necessary to cut
> it in half and do the 2nd half backwards (ie: for
> n=3, I would take care of the 1 2 1 - then 3 - then 1
> 2 1...but even then it seems like I could cut 1 2 1
> in half the same way and therefor I should be able to
> do ALL of it in single parts...
No, it's MUCH simpler than that. It's easier than yo uthink.
> Can someone veer me in the right direction here? I'm
> really lost with this.
Try this simpler version of the problem:
Write a recursive method that creates this output:
n = 1: 1
n = 2: 1 2
n = 3: 1 2 3
And try this simpler version:
n = 1: 1
n = 2: 2 1
n = 3: 3 2 1
Thank you so much...looking at this now.DM
Here's another hint: although recursive method examples usually involve integers, they don't have to just use integers.
Can you expand on this a bit? I understand the idea of recursion doesnt require integers directly - are you suggesting this for my problem or just in general?thank you again!
I'm pretty certain that for this problem, the value returned by your recursive method has to be a String. The argument to the method may or may not be.
I tried writing a version of this, and the return value was a String anyway. Offhand I can't think of a way to do this problem without the recursive method returning a String. (Well, you could use a list or something, but that would be harder than it needs to be.)
Message was edited by:
paulcw
Devo,
Sorry for cutting in... I think what paul is suggesting is that recursion is not limited to integer "operatives"... such as a recursive file find (search in winblows parlance)//pseudocode for recursive "depth first" file find
find(files[]) {
for each file in files
if file isa Directory then
find(filename/*)
else
print filename
endif
next file
}
but due to stack size limitations, the universal bane of recursive algorithms, this is most useful with integer (tiny wee small 32 bit thingummies) arguments.
... a recursive algorithm which uses a small number of integer args doesn't have to worry about StackFullException's
keith.
sorry paul we cross-posted... drunk skull... slow fingers... :-(
When I stare at your output I observe the following:1) the pattern for n == 1 is just 1;2) the pattern for n > 1 has that n in the middle of the pattern;3) left and right of that n are the pattern for n-1.kind regards,Jos
@paulcw: If I did the string method, would I just be concatenating the various strings? ie: str = str+ recPatPrint(n-1) + str? If I did this, how would I get the function itself to print the output?
@corlettk: I 'think' that is why I am trying to output on the fly, to avoid the overall overflows no matter the n value (I guess an n value that itself overflows is another story).
@JosAH: I noticed this pattern but am unsure how to replicate it...mainly due to not having a good stopping test...I end up getting an infinite 12121212 or something of the like. Not knowing the number previously written I think is part of the issue as I cant test to see if I already printed it.
public static void recPatPrint(int n) {
if (n==1)
System.out.print(1);
//if (n > 1) {
while (n>1) {
recPatPrint(n-1);
System.out.print(n);
}
}
This obviously puts it through an infinite loop between n=1 and 2. I am pretty sure I am overthinking this...I just cant figure out where.
Message was edited by:
Devin
Hint: there's no limit to how many times you can call "recPatPrint(n-1)"
> @JosAH: I noticed this pattern but am unsure how to replicate
> it...mainly due to not having a good stopping test...
Here's what I wrote in a previous reply:
1) the pattern for n == 1 is just 1;
2) the pattern for n > 1 has that n in the middle of the pattern;
3) left and right of that n are the pattern for n-1.
IMHO observation 1) is a perfect stopping test. Here's a spoiler:public void pattern(int n) { // assume n > 0
if (n <= 0) return;
pattern(n-1);
System.out.print(n);
pattern(n-1);
}
Note that no newline is printed by this method. Also note: no comments,
there should be something left to investigate ;-)
kind regards,
Jos
Thank you Jos,I hadn't recognized how a simple return statement on n<=0 would stop the looping for further up n value calls...I now have a love-hate relationship with recursion...Thank you everyone for your help!DM
> @paulcw: If I did the string method, would I just be
> concatenating the various strings? ie: str = str+
> recPatPrint(n-1) + str?
Well, you kind of have it revesed, but yes.
> If I did this, how would I
> get the function itself to print the output?
You wouldn't. The caller would print the result.
You can do it in such a way that you don't need two branches of the recursive invocations (i.e., so you don't call method(n-1) twice in the same method), and so you don't need any kind of formal memoizing system...you just store the recursive call in a local variable and use it twice...
