Fibonacci series recursion error

[Peter Otten]

harrismh777 wrote:

> 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)

Well, fib(10**5)[-1] has over 20000 digits, so I'd expect the runtime to be 
dominated by long-integer arithmetic. And that is identical for both 
scripts. You will get some improvement from switching to gmpy.

>     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...  ;-)

I take that as an indication that you are not Dutch ;) 

>     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)

I would not seriously recommend list(islice(generator, stop)) in that case, 
either, but I think my fib() is a good building block:

>>> from itertools import islice
>>> def cached_series(g):                                             
...     items = []                                                    
...     def f(n):                                                     
...             if n <= len(items):                                    
...                     return items[:n]                              
...             items.extend(islice(g, n-len(items)))
...             return items[:n]                     
...     return f                                     
...
>>> def _fib():
...     a = b = 1
...     while True:
...             yield a
...             a, b = b, a + b
...
>>> def _noisy():
...     for x in _fib():
...             print "calculating", x
...             yield x
...
>>> fib = cached_series(_noisy())
>>> fib(0)
[]
>>> fib(1)
calculating 1
[1]
>>> fib(5)
calculating 1
calculating 2
calculating 3
calculating 5
[1, 1, 2, 3, 5]
>>> fib(5)
[1, 1, 2, 3, 5]
>>> fib(6)
calculating 8
[1, 1, 2, 3, 5, 8]