Recursion or iteration (was Fibonacci series recursion error)

[Dave Angel]

On 01/-10/-28163 02:59 PM, rusi wrote:
> 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=) else (x * powR(x, n-1))
>
> is just python syntax for the school algebra (or Haskell) equations:
>
> x^0 =
> x^(n+1) =  * 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=) 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 ]
>

What I'm surprised at is that nobody has pointed out that the logn 
version is also generally more accurate, given traditional floats. 
Usually getting the answer accurate (given the constraints of finite 
precision intermediates) is more important than performance, but in this 
case they go hand in hand.

DaveA