Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #4534

Re: Recursion or iteration (was Fibonacci series recursion error)

Show key headers only | View raw

On 01/-10/-28163 02:59 PM, rusi wrote:
> 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=) 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

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Fibonacci series recursion error lalit <opposite800@gmail.com> - 2011-04-29 20:22 -0700
  Re: Fibonacci series recursion error Gary Herron <gherron@islandtraining.com> - 2011-04-29 20:41 -0700
  Re: Fibonacci series recursion error Jason Friedman <jason@powerpull.net> - 2011-04-30 03:57 +0000
  Re: Fibonacci series recursion error harrismh777 <harrismh777@charter.net> - 2011-04-29 23:45 -0500
    Re: Fibonacci series recursion error harrismh777 <harrismh777@charter.net> - 2011-04-29 23:51 -0500
      Re: Fibonacci series recursion error harrismh777 <harrismh777@charter.net> - 2011-04-30 00:31 -0500
        Re: Fibonacci series recursion error Peter Otten <__peter__@web.de> - 2011-04-30 08:14 +0200
          Re: Fibonacci series recursion error rusi <rustompmody@gmail.com> - 2011-05-02 00:08 -0700
    Re: Fibonacci series recursion error Hans Georg Schaathun <hg@schaathun.net> - 2011-04-30 06:50 +0100
    Re: Fibonacci series recursion error Paul Rudin <paul.nospam@rudin.co.uk> - 2011-04-30 06:43 +0100
  Re: Fibonacci series recursion error Ian Kelly <ian.g.kelly@gmail.com> - 2011-04-29 23:27 -0600
    Re: Fibonacci series recursion error harrismh777 <harrismh777@charter.net> - 2011-04-30 00:35 -0500
      Re: Fibonacci series recursion error Peter Otten <__peter__@web.de> - 2011-04-30 08:32 +0200
        Re: Fibonacci series recursion error Chris Angelico <rosuav@gmail.com> - 2011-04-30 16:37 +1000
      Re: Fibonacci series recursion error Thomas Rachel <nutznetz-0c1b6768-bfa9-48d5-a470-7603bd3aa915@spamschutz.glglgl.de> - 2011-04-30 11:37 +0200
        Re: Fibonacci series recursion error harrismh777 <harrismh777@charter.net> - 2011-05-02 16:50 -0500
          Re: Fibonacci series recursion error Chris Angelico <rosuav@gmail.com> - 2011-05-03 08:17 +1000
            Re: Fibonacci series recursion error harrismh777 <harrismh777@charter.net> - 2011-05-03 12:10 -0500
              Re: Fibonacci series recursion error Chris Angelico <rosuav@gmail.com> - 2011-05-04 07:41 +1000
              Re: Fibonacci series recursion error Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-03 16:31 -0600
              Re: Fibonacci series recursion error Chris Angelico <rosuav@gmail.com> - 2011-05-04 09:09 +1000
          Re: Fibonacci series recursion error Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-02 16:22 -0600
          Re: Fibonacci series recursion error Chris Angelico <rosuav@gmail.com> - 2011-05-03 08:42 +1000
          Recursion or iteration (was Fibonacci series recursion error) rusi <rustompmody@gmail.com> - 2011-05-02 18:48 -0700
            Re: Recursion or iteration (was Fibonacci series recursion error) Chris Angelico <rosuav@gmail.com> - 2011-05-03 12:13 +1000
            Re: Recursion or iteration (was Fibonacci series recursion error) Chris Angelico <rosuav@gmail.com> - 2011-05-03 15:29 +1000
              Re: Recursion or iteration (was Fibonacci series recursion error) rusi <rustompmody@gmail.com> - 2011-05-03 00:52 -0700
                Re: Recursion or iteration (was Fibonacci series recursion error) Dave Angel <davea@ieee.org> - 2011-05-03 06:32 -0400
                Re: Recursion or iteration (was Fibonacci series recursion error) rusi <rustompmody@gmail.com> - 2011-05-03 03:51 -0700
                Re: Recursion or iteration (was Fibonacci series recursion error) Chris Angelico <rosuav@gmail.com> - 2011-05-03 21:04 +1000
                Re: Recursion or iteration (was Fibonacci series recursion error) Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-03 12:49 +0000
                Re: Recursion or iteration (was Fibonacci series recursion error) Chris Angelico <rosuav@gmail.com> - 2011-05-03 23:02 +1000
            Re: Recursion or iteration (was Fibonacci series recursion error) Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-02 23:46 -0600

csiph-web