Recursion or iteration (was Fibonacci series recursion error)

[Ian Kelly]

On Mon, May 2, 2011 at 11:27 PM, Dan Stromberg <drsalists at gmail.com> wrote:
> 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.


It's linear as written.  I think you're talking about an
implementation like this one:

def powR(x,n):
  if n < 0:
    return 1.0 / powR(x, -n)
  elif n == 0:
    return 1
  else:
    half_n = n // 2
    root = powR(x, half_n)
    result = root * root
    if half_n + half_n == n - 1:
      result = result * x
    return result

That's O(log n), but it was harder to write, and it could just as
easily be iterative.  In fact it might actually have been a bit
simpler to write it iteratively.