<br><div class="gmail_quote">On Mon, May 2, 2011 at 7:13 PM, Chris Angelico <span dir="ltr"><<a href="mailto:rosuav@gmail.com">rosuav@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div class="im">On Tue, May 3, 2011 at 11:48 AM, rusi <<a href="mailto:rustompmody@gmail.com">rustompmody@gmail.com</a>> wrote:<br>
> What are their space/time complexities?<br>
> Which do you prefer?<br>
<br>
</div>They're pretty similar actually. If you rework the first one to not<br>
use range() but instead have a more classic C style of loop, they'll<br>
be almost identical:<br>
<div class="im"><br>
def powI(x,n):<br>
   result = 1<br>
</div>   while n > 0:<br>
       result *= x<br>
       n-=1<br>
   return result<br>
<br>
There's a subtle difference in that powR as you've coded it will<br>
infinite-loop if given a negative exponent, while powI in any form<br>
will simply return 1 (neither is technically correct, fwiw). Other<br>
than that, the only difference is that one keeps its state on the call<br>
stack, the other uses a temporary variable.<br></blockquote><div><br>The recursive solution uses more stack.  That is true.<br><br>But the recursive solution has time complexity of O(logn).  The iterative solution has time complexity of O(n).  That's a significant difference for large n - a significant benefit of the recursive version.<br>
<br>However, an iterative version of a function can always be created from a recursive version.  In this case, an iterative version can be constructed that is O(logn) time and O(1) stack.<br><br></div></div>