Public Group

# Cursed Recursives

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

## 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 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 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 on other sites
Quote:
 Original post by ShakedownWrite 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 on other sites
Quote:
Original post by TheUnbeliever
Quote:
 Original post by ShakedownWrite 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 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 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 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 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 on other sites
Quote:
 Original post by argonautTrue. 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.

• 16
• 9
• 13
• 41
• 15