Exponentiation – Calculate Pow(x,n) using recursion

27
13



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/

27 COMMENTS

  1. 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;
    }

  2. 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?

  3. 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)

  4. 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

  5. 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.

  6. You can add one more condition, which (for n >= 1) will save you one extra function call:
    if (n == 1) return x;

LEAVE A REPLY

Please enter your comment!
Please enter your name here