Recursion or iteration (was Fibonacci series recursion error)

[rusi]

On May 3, 10:29 am, Chris Angelico <ros... at gmail.com> wrote:
> On Tue, May 3, 2011 at 3:27 PM, Dan Stromberg <drsali... at 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 ]