Fibonacci series recursion error

harrismh777 harrismh777 at charter.net
Sat Apr 30 09:43:53 CEST 2011


Peter Otten wrote:
> For the record, the one true way to implement the Fibonacci series in Python
> is
>
>>>> >>>  def fib():
> ...     a = b = 1
> ...     while True:
> ...             yield a
> ...             a, b = b, a+b # look ma, no temporary variable

[snip]

I created two scripts, stressed them a bit, and then timed:
I called the two scripts fib.py and fib2.py... here they are:

==================begin fib.py============================
#!/home/marcus/bin/python3
def fib():
     a=b=1
     while True:
         yield a
         a,b=b,a+b   # look ma, no temporary variable

from itertools import islice
flist=list(islice(fib(), 100000))
==================end fib.py==============================


==================begin fib2.py===========================
#!/home/marcus/bin/python3
def fib(i=1):
     a=b=1;l=[]
     for j in range(0,i):
         l.append(a)
         a,b = b,a+b       # look ma,  I can do it too....
     return l

list=fib(100000)
==================end fib2.py=============================

   [ TIMES ]      1 core, 1.6 Ghz, 3196 bogomips

marcus at shire:~/Python3$ time ./fib.py

real	0m2.775s
user	0m1.908s
sys	0m0.820s


marcus at shire:~/Python3$ time ./fib2.py

real	0m2.796s
user	0m1.916s
sys	0m0.824s



    You will notice first that the times are *almost* identical. So, 
down under the heart of python, something is wrong. (never mind)

    But the really interesting thing I found is that when I coded away 
the temporary reference, 100ms of user time moved over to sys time. doh, 
must be that 'somewhere' a 'temporary' reference had to be created... 
and it doesn't look like it's optimized very well...

    But, this should also go to show you... that there is *never* just 
one obvious way to do anything...  contrary to the ZEN of Python...  ;-)


    On the other hand, I am very much interested in "yield," because of 
its obvious persistent state, On the other hand, I don't like you fib() 
function because it does not encapsulate the fib generator. I suppose 
you are considering whatever module is holding the fib() code as the 
encapsulation, but I thought the idea from the OP was to create a 
generator that could be called and return a list... this is a little goofy:
           list(islice(fib(), X))

when what was wanted is:

           list = fib(X)





kind regards,
m harris












More information about the Python-list mailing list