Sign in to follow this  

Cursed Recursives

This topic is 3861 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm currently reading "Learn C++ in 21 days" which a shockingly good book (despite the dreaded learn [blank] in [blank] amount of days title) and I've come across an exercise which demands a recursive function that passes a number to a power. And I have no idea how to write that function. The Instructions: Instructions: Write a program that asks for a number and a power. Write a reculsive function that takes the number to the power. Thus if the number is 2 and the power is 4, the function will return 16. Any ideas? tips? Thank you.

Share this post


Link to post
Share on other sites
Look into fast exponentiation. Also:

int function(int a, int b)
{
if (...)
{
// In a trivial situation, return the solution directly
return (...);
}

else
{
// In a complex situation, solve recursively smaller
// subproblems.
int c = function(...,...);
return (...);
}
}

Share this post


Link to post
Share on other sites
Write a function that accepts 2 int parameters. Like power( int a, int b ), then use a for(...;...;...) loop using the two integers to multiply the first integer an amount of times equal to the second integer.
So if you called power( 2, 4 ), then it would run through a for loop 4 times, each iteration multiplying 2 by 2 ( so you'd get 2x2x2x2 ).

Share this post


Link to post
Share on other sites
Quote:
Original post by Shakedown
Write a function that accepts 2 int parameters. Like power( int a, int b ), then use a for(...;...;...) loop using the two integers to multiply the first integer an amount of times equal to the second integer.
So if you called power( 2, 4 ), then it would run through a for loop 4 times, each iteration multiplying 2 by 2 ( so you'd get 2x2x2x2 ).


The exercise is to use recursion not iteration.

Share this post


Link to post
Share on other sites
Quote:
Original post by TheUnbeliever
Quote:
Original post by Shakedown
Write a function that accepts 2 int parameters. Like power( int a, int b ), then use a for(...;...;...) loop using the two integers to multiply the first integer an amount of times equal to the second integer.
So if you called power( 2, 4 ), then it would run through a for loop 4 times, each iteration multiplying 2 by 2 ( so you'd get 2x2x2x2 ).


The exercise is to use recursion not iteration.


Ha good call

Share this post


Link to post
Share on other sites
Something like this?


int function(int i, int power)
{
if(--power)
i *= function(i, power);
return i;
}






*fixed*

I dunno, too early for my brain to functionalize recursion. Oh snap ... its 13:21 :)

[Edited by - argonaut on May 19, 2007 2:08:02 PM]

Share this post


Link to post
Share on other sites
The key to understanding recursion lies in finding a pattern in your problem.

Say you want to compute 25. Is there a way to define 25 using another exponential expression? Well, 25 can be translated into (2 * 24), right? Furthermore, 24 can be expressed as (2 * 23). Similarly, 23 can be expressed as (2 * 22). See a pattern?

So, back to our example, you want to calculate 25 using (2 * 24). Do you have a function to compute exponents by any chance?

The next thing to identify is the base case. What is the condition that will stop the function from calling itself? In your case, what is the smallest exponent that can not be expressed as (n * nn - 1)?

Hope this helps.

Share this post


Link to post
Share on other sites
Except that (EDIT: referring to argonaut's suggestion) doesn't handle ab for b = 0 (EDIT: changed from b < 2, I'm not sure if you changed your post or if I just misread it).

You're looking for something to fit ToohrVyk's framework very closely (including handling the trivial/special cases mentioned above and recursing otherwise).

[Edited by - TheUnbeliever on May 19, 2007 2:28:26 PM]

Share this post


Link to post
Share on other sites
True. I didn't build in handling for power == 0 (or negative powers, for that matter). However, the methodology is correct.

I think that Darklighter provides a very good explanation of recursion.

Share this post


Link to post
Share on other sites
Quote:
Original post by argonaut
True. I didn't build in handling for power == 0


Yeah, sorry -- either I misread your post or you've edited it. I could have sworn that it previously didn't work for an exponent of 1 either.

Quote:
(or negative powers, for that matter). However, the methodology is correct.


Or indeed rational powers ;-) But I think the exercise would be looking primarily for the naturals. I agree the method is sound, although I think you're better treating the 0 case as the end case.

Share this post


Link to post
Share on other sites
Quote:

Or indeed rational powers ;-) But I think the exercise would be looking primarily for the naturals. I agree the method is sound, although I think you're better treating the 0 case as the end case.


I agree 100%, which is why I personally don't believe this is a good exercise to demonstrate the usefulness of recursion, since (ideally) too many conditions must be checked for within the recursive function. But then again, I haven't written any C++ books, so who am I to judge :)

Share this post


Link to post
Share on other sites
Quote:
Original post by argonaut
Something like this?

*** Source Snippet Removed ***

*fixed*

I dunno, too early for my brain to functionalize recursion. Oh snap ... its 13:21 :)


Hmm that wouldn't work , power(2,0) should return 1, not 2 as your would.

perhaps something like ....

int power(int i, unsigned int p) {
if (p>0) return i*power(i,p-1);
else return 1;
}



Share this post


Link to post
Share on other sites
Quote:
Original post by argonaut
Quote:

Or indeed rational powers ;-) But I think the exercise would be looking primarily for the naturals. I agree the method is sound, although I think you're better treating the 0 case as the end case.


I agree 100%, which is why I personally don't believe this is a good exercise to demonstrate the usefulness of recursion, since (ideally) too many conditions must be checked for within the recursive function.


Indeed. Another exercise I'd suggest the OP tries if they want would be the factorial function, that's the one that looks like
0! = 1
1! = 1 * 1 = 1
2! = 2 * 1 = 2
3! = 3 * 2 = 6
4! = 4 * 6 = 24
5! = 5 * 24 = 120
...

Share this post


Link to post
Share on other sites
To understand recursion you must first understand recursion.
The best way to do a power function is to cut the powers in half like such

x^n = x^(n/2) * x^(n/2);
there are two cases that will happen when n is odd and when n is even
you have to mod it to find out if it's even or odd so if mod(n, 2) = 0
then it is even and you just do
x^(n/2) * x^(n/2);
and if it's odd then you do
x^(n/2) * x^(n/2) * x;

here is an example:

double power(double x, int n)
{
double exp;
if(x == 0)
{
if(n < 0)
return 0;
}
else if (n == 0)
return 1;

else if (n > 0)
{
exp = power(x, n/2);
exp *= exp;
if (n % 2 > 0)
exp *= x;
return exp ;
}
else if (n < 0)
{
exp = power(x, -n/2);
exp *= exp;
if(-n % 2 > 0)
exp *= x;
return 1/exp;
}
}

[Edited by - Darken Mind on May 19, 2007 5:06:50 PM]

Share this post


Link to post
Share on other sites
p.s. any problem that can be solved with recursion can be solved with
iteration, however sometimes it's much much simpler to use recursion.
The real gains from using recursion is simplicity and or running time
for instance the function that just showed runs in big O(log n) time
where iteration runs in big O(n) time. Which means that one runs in logarithmic time versus linear time.

Share this post


Link to post
Share on other sites
Quote:
Original post by guardian24
Some say never demonstrate recursivity on problems that can be solved easily with iteration. So, Towers of Hanoi all the way!



# Discs are numbered 1 through N, smallest to largest.
to check_parity(disc, pole, N):
if pole is not empty: return disc % 2 == (disc at top of pole) % 2.
if pole != start pole: return false.
return disc % 2 == (N + 1) % 2.

to hanoi(N):
possible moves: (1->2), (1->3), (2->1), (2->3), (3->1), (3->2).
previous move = nil.
Repeat (2**N)-1 times:
candidate move = nil.
disc to move = 0.
For each move in possible moves:
my disc = disc that would be moved by this move.
If move is inverse of previous move: continue.
If my disc > disc at top of target pole: continue.
If check_parity(my disc, target pole, N): continue.
If disc to be moved > my disc:
disc to move = my disc.
candidate move = move.
Assert candidate move != nil.
previous move = candidate move.
Make candidate move.


OK, I guess it's not *easy* [grin]

Share this post


Link to post
Share on other sites
Quote:
Original post by guardian24
Some say never demonstrate recursivity on problems that can be solved easily with iteration. So, Towers of Hanoi all the way!


Some say never demonstrate recursivity in languages that suck at being recursive. [wink]

Share this post


Link to post
Share on other sites

This topic is 3861 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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