#Recursive power function

23 messages · Page 1 of 1 (latest)

fleet umbra
#

so this exercise is in the book i'm using to learn C, and i'm not finding the solution to make it work, this is the code i have rn (not working like it should)

int power(int x, int n)
{
    if (n == 0)
        return x;
    else
    {
        if(n % 2 == 0)
            return x * power(x, n / 2);
        else
            return x * power(x, n - 1);
    }
}
image.png
delicate shuttleBOT
#

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question use !howto ask.

wintry wind
mild glacier
#

Okay, so this code can't work.
Think about it: What happens if you have e.g. power(2, 8).
Then what happens in your code is:

 power(2,8)                            
 │=>                                   
 │  2 * power(2,4)                     
 │    │  =>                            
 │    │    2 * power(2,2)              
 │    │      │  =>                     
 │    │      │    2 * power(2,1)       
 │    │      │      │  =>              
 │    │      │      │    2 * power(2,0)
 │    │      │      │      │  =>       
 │    │      │      │      │    2      
 │    │      │      │      4  <=       
 │    │      │      8    <=            
 │    │     16    <=                   
 │   32   <=                           
64 <=
#

Logically it can't make sense that x * pow(x, n - 1) is the same as x * xⁿ⁻¹ and that x * pow(x, n / 2) is the same as (x^(n/2))²

fleet umbra
#

omg it's confusing for me lol

wintry wind
#

read what the text says; they give you the formula when n is odd, when it is even, and when it is 0

mild glacier
#

Really, the reason why recursive functions are cool is because you can just assume them to work.
E.g. when you do power(x, n / 2), then you can assume that this correctly calculates x^(n/2) and if you write power(x, n - 1) then you can assume that this correctly calculates xⁿ⁻¹.
So in your code the even case would be power(x, n - 1) * power(x, n - 1) whereas the odd case would be x * power(x, n - 1)

wintry wind
#

power(x,n/2) * power(x,n/2) you mean

mild glacier
#

Recursive functions are really like induction proofs

mild glacier
fleet umbra
#

okay... i still don't understand, but i will be using your messages to see if it clicks or sum, thanks guys!

#

!solved

delicate shuttleBOT
#

Thank you and let us know if you have any more questions!

This thread is now set to auto-hide after an hour of inactivity

fleet umbra
#

okay guys, i'm dumb, my problem was that i returned x when n was 0 @wintry wind @icy shadow

#

thank you tho LOL

#

i literally tried eveything before posting, so i could have been right since the start but i'm just dumb as hell

wintry wind
#

I think the %2==0 branch is still wrong though

#

(and when I say "I think", it's an euphemism 😄 )

fleet umbra
#

yeah, you are right

fleet umbra
fleet umbra
icy shadow