Which is more efficient way of performing powers (in terms of time complexity), using recursion, using while-loop, or both?

I've seen code examples of "divide-and-conquer" algorithms (or, at least what I think are "divide-and-conquer") - one general group of examples tend to use recursion while the other开发者_开发技巧 uses a while-loop.

Here's the recursion example:

...
if (exponent%2==0) 
{ 
return Power(base*base, exponent/2); 
} 
else if (exponent%2==1)
{ 
    return base*Power(base*base, exponent/2); 
} 
...

And, here's the while-loop example:

...
while (exponent>1)
{
    if (exponent%2 == 1)
        result *= base;
    exponent/=2;
    base *= base;
}
...

In both cases, it really looks like they're executed with the same number of operations. The number of operations that both approaches seem to take is bound by the ceiling function of T(exponent) = Θ(log_2(exponent)). Unless my analysis is wrong, I don't see how one approach is any faster than the other. I imagine that the recursion approach is less efficient than the while-loop approach in terms of space-complexity because the recursive approach would have a space complexity of 2*(log_2(exponent)) (if that analysis is correct).

Is the only advantage with the while-loop approach is that it has a lower space requirement?

---

Assuming that the compiler you're using is sane, then yes... the lower space requirement is the only advantage.

Note that most compilers allow for effective handling of tail recursion, which occurs when the function only calls itself as the last step of execution (see the article for examples). As written above, your recursion algorithm isn't tail recursive because the last step taken before returning is a multiplication (base*Power), but this can be changed by adding an accumulator variable as an argument which gets multiplied at each call and then returning the final accumulator that you attain.

Example code:

...
int Power(int base, int exponent, int accumulator)
{
    if (exponent%2==0) 
    { 
        return Power(base*base, exponent/2, accumulator); 
    } 
    else if (exponent%2==1)
    { 
        return Power(base*base, exponent/2, accumulator * base); 
    } 
}
...

where Power is always initially called with accumulator 1 (you can make an alternate function power(a,b), for example, that just calls Power(a,b,1) if needed).

---

The version with recursion is good for dydactical purposes, but the loop version is faster.

It's not only because of call overhead, but because loops can be unrolled by compiler, and the data dependency can be propagated easier.

---

For the powers problem --- yes, loops are probably better thanks to scope for compiler optimization. But you must realize that this does not apply to all divide-and-conquer algorithms (in case that's what you're implying in the first paragraph).

Also, don't forget, some divide-and-conquer paradigms work extremely well in distributed systems.

---

The concept of time complexity seems to be a bit off in your question.

If you're thinking about the question "How long will this function run" then the concept of time complexity has no meaning really. You seem to understand the basics, so you know that the complexity of 1000N + 100000 the same as for N/10000. That said, I'll also note that the time-cost for 1000N + 100000 is much greater then that for N/10000.

The concept of complexity relates to growth. It expressed the speed at which the function's time-consumption grows with the size of N (the size of the input data).

In the world of time-cost, the looping method will overthrow the recursive one in most cases (I don't think I've yet to see a case in which a recursive solution will take less time, even under compiler optimizations). Also, as you (and most posters before me) mentioned, the space required might be greater (if no tail-call optimization is used, it has to be notably greater).

If you wonder what's recursion is good for (outside of school), then the answer would be code simplicity (recursion can make for amazingly simple code at times, if used correctly).

---

this while loop example to calculate power of base is wrong it will calculate base^log(exponent) instead of base^exponent

* divide and conquer method using recursion will give Time complexity : O(logn) * using loop n-1 time multiplication operation will occur so TC : O(n)

if u have brain u can decide which one is better in terms of time.