On May 3, 10:29 am, Chris Angelico <ros...@gmail.com> wrote: > On Tue, May 3, 2011 at 3:27 PM, Dan Stromberg <drsali...@gmail.com> wrote: > Doh.
> Usually when someone gives a recursive solution to this problem, it's > O(logn), but not this time. > Here's a logn one: :-) Ok so you beat me to it :D I was trying to arrive at an answer to the question (by M Harris) about why anyone would do something like fib recursively. I used power since that illustrates the case more easily, viz: A trivial power -- recursive or iterative -- is linear time -- O(n) A more clever power can be O(log(n)) This more clever power can be trivially derived from the recursive one as follows: The recursive O(n) function: def powR(x,n): return 1 if (n==0) else (x * powR(x, n-1)) is just python syntax for the school algebra (or Haskell) equations: x^0 = 1 x^(n+1) = x * x^n Adding one more equation: x^(2*n) = (x^2)^n = (x*x)^n Re-python-ifying we get: def pow(x,n): return 1 if (n==0) else pow(x*x, n/2) if even(n) else x*pow(x,n-1) def even(n): return n % 2 == 0 Can this be done iteratively? Of course but its not so trivial. [If you believe it is, then try writing a log(n) fib iteratively :D ] -- http://mail.python.org/mailman/listinfo/python-list