CODEWITHSUNDEEP
c++algorithmrecursion
Aaron B
Aaron B

Reputation: 97

Recursion solution for a number raised to an exponent

Hey I have a problem were I have to solve x^n in a number of ways. One of them involves using a recursion formula and its giving me a hard time. So one of the ways I used recursion for x^n for n>=0

int power2(int base, int power){
    if (power == 0)
        return 1;
    else if ( power == 1)
        return base;
    else 
        return (base * power2(base, power - 1));
}

this makes sense to me So when i set X = 2 and N = 4, it is decreasing the power, which is acting as a counter, and doing 2x2 power raised to 3, 4*2, power raised to 2, 8 *2 = 16. Than the power is raised to 1, and I have a base case were if the power is raised to 1 it just returns base. However for my next one I have to solve it using three formulas.

So what I have so far is

int power3(int base, int power){
    if(power == 0){
        return 1;
    }
    else if ( power == 1)
        return base;
    // if power is even
    if (power % 2 == 0){
        return base*(power3(base,(power/2)));
    }
    // if power is odd
    else{
        return 0;
    }
}

So im just trying to get even numbers to work first, and when I set x=2 and n=4 it returns 8. Which makes sense to me, since when the power is 4/2 will only loop twice for being >1. So i really am trying to figure out a way to get this to loop one more time while staying true to the formula I was given.and when I added the odd base case now the program will work up untill n^5 but n^6 returns 32

Upvotes: 3

Views: 2433

Answers (1)

AliciaBytes
AliciaBytes

Reputation: 7439

You got a little problem with the interpretation of the formula.
x^n if n is even = [x^n/2]2 doesn't mean:

base*(power3(base,(power/2))) //meaning x * [x^n/2]

rather you'd have

(power3(base,(power/2))) * 2

looking at your formula again it isn't correct even and should be x^n if n is even = [x^n/2]^2

so as code:

(power3(base,(power/2))) * (power3(base,(power/2)))

or:

(power3(base * base,(power/2)))

Your whole function should probably be like this:

int power3(int base, int power){
    if(power == 0){
        return 1;
    }
    else if ( power == 1) // you don't really need this case,
        return base;      // power == 0 is enough as base case
        // if power is even
    if (power % 2 == 0){
        return (power3(base * base,(power/2)));
    }
    // if power is odd
    else{
         return base * (power3(base * base,(power/2)));
    }
}

Ok, since you seem to still be confused with the odd powers.
Your power variable is int so you get integer division meaning 3/2 = 1 instead of 1.5 (everything behind the decimal point gets truncated).

Now lets look at the odd case in the function:

return base * (power3(base * base,(power/2)));

lets assume base == 4 and power == 5

return 4 * (power3(4 * 4,(5/2))); // 5/2 evaluates to 2

is the same as saying return 4 * (power3(4, 5 - 1)) and then having return (power3(4 * 4, 4 /2)) since we now got an even case.

We basically just do these 2 steps as 1. I think my explanation sounds a bit weird but hope it helps.

Upvotes: 4

Related Questions