Sign in to follow this  
ahung89

[java] can any of you solve this?

Recommended Posts

Hey guys... pretty new to java here. I took one semester in school and now that it's winter break I've been studying on my own. I recently came across a really tough exercise (well, maybe not tough for y'all) on recursion that I've been wracking my brain but don't know how to solve. Here it is: "Write a recursive method called starString that accepts an integer as a parameter and prints to the console a string of stars (asterisks) 2 to the nth power long. For example: starString(0) should print * starString(1) should print ** starString(2) should print **** starString(3) should print ******** etc" I just can't think of any solution that doesn't involve using a for loop! Any help would be appreciated! Also any tips on solving future problems like this would be great... I need to learn to think like a programmer.

Share this post


Link to post
Share on other sites
Quote:

can any of you solve this?

Yes.

Quote:

Write a recursive method ... I just can't think of any solution that doesn't involve using a for loop!

Have you ever used recursion before?

Try something simpler:

Write a recursive function to count from 5 down to 0.

When you have that done, see if you can apply the same techniques to the other problem.

Share this post


Link to post
Share on other sites
public static void countDown(int n) {
if(n >= 0) {
System.out.print(n);
countDown(n - 1);
}
}

The way I solved most of the exercises so far that are like this is by calling the function again but subtracting a bit. But the thing is in the problem I mentioned I don't really see how this principal would apply, since I'm using an int. I guess I'll think a little harder though.

Share this post


Link to post
Share on other sites
First of all, I assume you know what recursion is. If not, google it and read up on it.

If yes, here's a hint: when thinking about recursion, you should try to look for the result of the previous recursion step in the result of the following recursion step. If you notice a pattern like that, it should be pretty straightforward to write it down as a function.

Let me know if you come up with something, and we'll go from there.

As for "learning to think like a programmer", e.g. analytical thinking + knowing your tools, is something that only comes with practice. Lots of practice.
When you wrap your head around this problem, try solving the Hanoi towers problem with recursion. Once you figure that one out, you pretty much have recursion covered and one step closer to a good analytic mindset :)

EDIT: too slow, but most of it still applies

Share this post


Link to post
Share on other sites
write a function that takes an int and prints 1 star when the input it receives is zero. Then write a function that prints two stars when it receives an input of 1(using the previous function that prints 1 star when it receives zero.) Now see if you can combine the two functions to give you the answer you seek.(Hint multiple recursive calls are allowed.)

Share this post


Link to post
Share on other sites
Thanks for the tips guys. I'm thinking I have a base case that calls starString sending 2^n as the parameter, with the condition that this hasn't been done yet. And the other case just calling starString(n-1), and a print('*') after that. Am I on the right track?

Share this post


Link to post
Share on other sites
I guess I could use a global boolean, there's gotta be an easier way though. Stonemetal thanks for the reply. I didn't read it though... I've changed my mind, I don't wanna give up on solving this myself yet.

Share this post


Link to post
Share on other sites
Quote:
Original post by ahung89
Thanks for the tips guys. I'm thinking I have a base case that calls starString sending 2^n as the parameter, with the condition that this hasn't been done yet.
Nope, you are making it too hard. Well you could but there is a simple recursive solution.
Quote:
And the other case just calling starString(n-1), and a print('*') after that. Am I on the right track?


Seriously though try writing a function that works only for an input of zero. Then an input of one and only call the function for the zero case solution. no odd globals needed.

Share this post


Link to post
Share on other sites
Quote:
Original post by stonemetal
write a function that takes an int and prints 1 star when the input it receives is zero. Then write a function that prints two stars when it receives an input of 1(using the previous function that prints 1 star when it receives zero.) Now see if you can combine the two functions to give you the answer you seek.(Hint multiple recursive calls are allowed.)


If I understand your post correctly, what you're proposing will not print n stars, but will print (1 + 2 + 3 .. + n) stars, which is incorrect.

There is only one function that needs to be written for this problem to be solved.

Share this post


Link to post
Share on other sites
Quote:
Original post by Grafalgar
Quote:
Original post by stonemetal
write a function that takes an int and prints 1 star when the input it receives is zero. Then write a function that prints two stars when it receives an input of 1(using the previous function that prints 1 star when it receives zero.) Now see if you can combine the two functions to give you the answer you seek.(Hint multiple recursive calls are allowed.)


If I understand your post correctly, what you're proposing will not print n stars, but will print (1 + 2 + 3 .. + n) stars, which is incorrect.

There is only one function that needs to be written for this problem to be solved.


nope I purpose the functions:
PrintStarLevelZero(int a)
{
if a == 0
print "*"
}

PrintStarLevelOne(int b)
{
if b == 1
{
PrintStarLevelZero(b-1)
PrintStarLevelZero(b-1)
}
}

which will function as printstar is supposed to for inputs 1 and 0. From here it should not be a large jump to the single function general solution that does what OP wants.

Share this post


Link to post
Share on other sites
Quote:
Original post by ahung89
public static void countDown(int n) {
if(n >= 0) {
System.out.print(n);
countDown(n - 1);
}
}


This is 99% of the solution already. Think about it: how many numbers will this function print out? What do you want to print out instead of numbers?

Share this post


Link to post
Share on other sites
hey stonewall - the exercise only allows me to write one method.

Also, I forgot to specify, it's supposed to throw an IllegalArgumentException if passed something less than 0 (which sucks because I was thinking about going backwards and calling the function with a negative 2 to the n, and adding 1 each time).

One question before I leave to solve this on my own - am I going to have to use anything more advanced than basic operators? Will I have to use the math class's power or root methods? Also do I need a for loop? Because I can think of many ways that involve for loops but I think that'd defeat the purpose of the exercise.

thanks... this problem's driving me absolutely crazy

Share this post


Link to post
Share on other sites
Quote:

One question before I leave to solve this on my own - am I going to have to use anything more advanced than basic operators? Will I have to use the math class's power or root methods? Also do I need a for loop? Because I can think of many ways that involve for loops but I think that'd defeat the purpose of the exercise.


No, you don't need a loop and you don't need any math functions. It can be done [smile]

Share this post


Link to post
Share on other sites
arghhh alright i'm going to spend all night solving this if i have to. thanks for not satisfying my urge to get the answer right away, i know it'll help me more when i figure it out on my own. i'm not going to check this thread any more until i get the answer.

Share this post


Link to post
Share on other sites
Quote:
Original post by ahung89
Thanks for the tips guys. I'm thinking I have a base case that calls starString sending 2^n as the parameter, with the condition that this hasn't been done yet. And the other case just calling starString(n-1), and a print('*') after that. Am I on the right track?


This would work, but the conditions of the problem state that you should give n as the parameter, not 2^n.

stonemetal is giving you a pretty good suggestion.

Notice the whole 'power of two' thing, and how in his example, PrintStarLevelOne calls PrintStarLevelZero twice. Now, if we were one PrintStarLevelTwo, what do you think it would do? It could call PrintStarLevelZero 2^2 times ... or we could take a look at PrintStarLevelOne and see that it already prints two stars. So we could just call that twice, right?

In fact, printing 2^n stars is really just printing 2^(n-1) stars twice...isn't it?

You can probably get it from there...

Share this post


Link to post
Share on other sites
Try to think of it like a complete tree
|-----/\-----|
|---/\ /\---|
|--/\/\/\/\--|
Each level of the tree is one recursion.
Notice how the number of leaves corresponds to each level and try breaking the problem up into subtrees and think about how the simplest subtrees would be solved.

Share this post


Link to post
Share on other sites
you guys are going to hate me, but after hours of trying I asked my dad who is a computer science/math major to help me and he figured it out in less than 30 seconds...

i just had to make it so that if n = 0 it draws a star, then call the function with n-1 twice... wow i feel stupid. I'm trying right now to fully understand how it works. He drew a tree similar to the one EAX did. I can see now why it works, I don't know how the hell he figured that out so fast. Exponents just confuse the hell out of me. Oh well, all part of learning I guess.

Share this post


Link to post
Share on other sites
Quote:
Original post by ahung89
you guys are going to hate me, but after hours of trying I asked my dad who is a computer science/math major to help me and he figured it out in less than 30 seconds...

i just had to make it so that if n = 0 it draws a star, then call the function with n-1 twice... wow i feel stupid. I'm trying right now to fully understand how it works. He drew a tree similar to the one EAX did. I can see now why it works, I don't know how the hell he figured that out so fast. Exponents just confuse the hell out of me. Oh well, all part of learning I guess.


If you focus too hard on the exponent you'll overthink the problem. The way I figured it out was to draw the the results on a piece of paper first:

0 = *
1 = **
2 = ****
3 = ********

Then, looking at it (forgetting about exponents), you can see that each increasing value just prints out twice as many stars than the previous value:

0 = *
1 = *,* // twice "0"
2 = **,** // twice "1"
3 = ****,**** // twice "2"

The only one that isn't "twice" the previous, is 0. So, I knew that the first thing my function should check for is n == 0:


void printStars(int n)
{
if(n == 0)
{
cout << "*";
return;
}
}




Then, looking at "1", I realize that I just need to do "0" twice. And if I get "2", I just need to do "1" twice, and if I get "3", do "2" twice, and so and on. The common pattern here? Just do the previous value twice, and print a star if you get zero.


void printStars(int n)
{
if(n == 0)
{
cout << "*";
return;
}

printStars(n - 1);
printStars(n - 1);
}




The point is - this was all figured out without me really focusing on the 2^n part, and chances are neither did your dad.

Problems like these are good ones - you learn to focus on the problem itself and ignore the parts that make it sound more complicated than it is.

Share this post


Link to post
Share on other sites
Thanks for the explanation. I definitely learned a lot from it, and from this whole experience. Whole time I was thinking about how to manipulate the argument I sent as n.... when all I had to do was call it twice. It works out so perfectly...

This is why I love programming, the solutions are so elegant and just test your logic/problem solving skills.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this