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

Groups > comp.lang.python > #87860

Re: fibonacci series what Iam is missing ?

Show key headers only | View raw

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

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

Thread

Re: fibonacci series what Iam is missing ? Terry Reedy <tjreedy@udel.edu> - 2015-03-23 21:45 -0400

csiph-web