Recursion or iteration (was Fibonacci series recursion error)

[Dan Stromberg]

On Mon, May 2, 2011 at 7:13 PM, Chris Angelico <rosuav at gmail.com> wrote:

> On Tue, May 3, 2011 at 11:48 AM, rusi <rustompmody at 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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20110502/bca78819/attachment-0001.html>