Jump to content
  • Advertisement
Sign in to follow this  
Sarxous

Cursed Recursives

This topic is 4198 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
Advertisement
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!