See complete series on recursion here

In this lesson, we have described two different recursive algorithms to calculate x^n ( x to the power n)

Prerequisite: Basic knowledge of recursion in programming.

Nguồn:https://dothihoa.com/

See complete series on recursion here

In this lesson, we have described two different recursive algorithms to calculate x^n ( x to the power n)

Prerequisite: Basic knowledge of recursion in programming.

Nguồn:https://dothihoa.com/

this one is even better

int power(int x, unsigned int y)

{

int temp;

if( y == 0)

return 1;

temp = power(x, y/2);

if (y%2 == 0)

return temp*temp;

else

return x*temp*temp;

}

int main() {

printf("%d",power(2,2));

return 0;

}

What would be the Time complexity ?

How does y <– pow(x,n/2) work? How does he program know it needs to multiply x? If n = 8 it gets divided unless n reaches 2/2 = 1. How does the program know it needs to multiply the x's and not just add them?

Damn, Pinto is my firend and not me.

wheres the code

I've never thought about this way !!

Is this for java

for the odd case, we can use x*pow(x,n/2)*pow(x,n/2) that will work better than x*pow(x,n-1).

your explanation is so amazing thank you so much man

Hey, this doesnt handle the case where n is negative

How does java know pow(x,n-1)== x^n-1??

thanks, nice explanation !

simply the best

couldn't but comment…..very nice explanation ..thanks a lot

is Albert's algorithm an example of divide and conquer?

For people who are confused that in odd case, it will be O(n):

It is still O(log n) because in next call, n will become even.

P(17) => P(16) => P(8) => P(4) => P(2) => P(1) => P(0)

P(15) => P(14) => P(7) => P(6) => P(3) => P(2) => P(1) => P(0)

You can actually tweak the odd case as: x^((n-1)/2) * x^((n-1)/2) * x [as (n-1)/2 + (n-1)/2 + 1 = n]. It will still be O(log n) but the number of calls would reduce a bit. It is also now evident from the looks of the expression that it will be O(log n).

P(17) => P(8) => P(4) => P(2) => P(1) => P(0)

P(15) => P(7) => P(3) => P(1) => P(0)

After calling the base case(x^0), how does it find (x^(n/2))?

dude.. nice videos you make …. just arrange them in sequence… like after this there should be the calculation of time complexities but next video in the list is modular exponentiation… thanks

How is Pinto's solution O(log n)?

It still O(n) in case of odd numbers. Shouldn't it be Ω(log n) since it's a lower bound.

You can add one more condition, which (for n >= 1) will save you one extra function call:

if (n == 1) return x;Which software do you use?I also wish to make some competitive coding videos.

Awesome explanation, thank you!!!

you are awesome man !

Now I believe the author who said when you look at recursive code for the first time it looks like black magic.

Can't thank you enough 🙂 great vids … keep it up

Very well explained and very interesting! Thank you for these videos!

Thanks Anshul !