Path: csiph.com!usenet.pasdenom.info!news.redatomik.org!newsfeed.xs4all.nl!newsfeed2a.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
To: python-list@python.org
From: Terry Reedy <tjreedy@udel.edu>
Subject: Re: fibonacci series what Iam is missing ?
Date: Mon, 23 Mar 2015 21:45:25 -0400
References: <CACT3xuVF-MOVQK5wSorRSAfpAQEXvS7QsqarACVZKXsQ0bxzpQ@mail.gmail.com> <CAPTjJmrRv+DQGpzdY5te-vk_u9p5AzWYQ-6B=m1knPoaXpRmRQ@mail.gmail.com> <55105EF4.2070805@davea.name> <meq5i2$53s$1@ger.gmane.org> <55109DEF.9070001@davea.name>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 7bit
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:31.0) Gecko/20100101 Thunderbird/31.5.0
In-Reply-To: <55109DEF.9070001@davea.name>
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.91.1427161553.10327.python-list@python.org>
Lines: 68
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:87860

On 3/23/2015 7:12 PM, Dave Angel wrote:
> On 03/23/2015 06:53 PM, Terry Reedy wrote:

>> Iteration with caching, using a mutable default arg to keep the cache
>> private and the function self-contained.  This should be faster.
>>
>> def fib(n, _cache=[0,1]):
>>      '''Return fibonacci(n).
>>
>>      _cache is initialized with base values and augmented as needed.
>>      '''
>>      for k in range(len(_cache), n+1):
>>          _cache.append(_cache[k-2] + _cache[k-1])
>>      return _cache[n]
>>
>> print(fib(1), fib(3), fib(6), fib(5))
>> # 1 2 8 5
>>
>> Either way, the pattern works with any matched pair of base value list
>> and recurrence relation where f(n), n a count, depends on one or more
>> f(k), k < n.  'Matched' means that the base value list is as least as
>> long as the maximum value of n - k.  For fib, the length and max are
>> both 2.
>>
>
> I almost used a default value as a cache, but didn't want to confuse the
> OP.  Also, your present code does not use recursion, so probably
> wouldn't make the prof happy.

I did not read the initial posts with that requirement.  Iteration is 
easily converted to tail recursion, which is definitely the way to 
calculate recurrences with more than one term without a full cache.

> On the other hand, my loop makes some non-obvious assumptions, like that
> append is always the right place to put a new value.  I knew it'd  work,
> since fib calls itself with n-1.  But it wouldn't directly work if the
> function had recursed on n-2 and n-3.  Yours would.
>
> I prefer iteration, but I still figure this is an assignment.

def fib(n, _cache=[0,1]):
     '''Return fibonacci(n).

     _cache is initialized with base values and augmented as needed.
     '''
     k = len(_cache)  # min n without a value in cache
     if k <= n:
         _cache.append(_cache[k-2] + _cache[k-1])
         return fib(n)
     else:
         return _cache[n]

print(fib(1), fib(3), fib(6), fib(5))
# 1 2 8 5

If one does not like the append as a statement, and prefer it as part of 
the return expression, this works too.

def fib(n, _dummy=None, _cache=[0,1]):
     k = len(_cache)
     return (fib(n, _cache.append(_cache[k-2] + _cache[k-1]), _cache)
                if k <= n else _cache[n])

However, I am not a fan of puritanical functionalism.

-- 
Terry Jan Reedy