On Mon, May 2, 2011 at 7:13 PM, Chris Angelico <ros...@gmail.com> wrote:
> On Tue, May 3, 2011 at 11:48 AM, rusi <rustompm...@gmail.com> wrote: > > What are their space/time complexities? > > Which do you prefer? > > They're pretty similar actually. If you rework the first one to not > use range() but instead have a more classic C style of loop, they'll > be almost identical: > > def powI(x,n): > result = 1 > while n > 0: > result *= x > n-=1 > return result > > There's a subtle difference in that powR as you've coded it will > infinite-loop if given a negative exponent, while powI in any form > will simply return 1 (neither is technically correct, fwiw). Other > than that, the only difference is that one keeps its state on the call > stack, the other uses a temporary variable. > The recursive solution uses more stack. That is true. 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. 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.
-- http://mail.python.org/mailman/listinfo/python-list