fibonacci series what Iam is missing ?

[Dave Angel]

On 03/23/2015 06:53 PM, Terry Reedy wrote:
> On 3/23/2015 2:44 PM, Dave Angel wrote:
>
>> ## Example 2: Using recursion with caching
>> cache = [0, 1]
>> def fib4(n):
>>      if len(cache) <= n:
>>          value = fib4(n-2) + fib4(n-1)
>>          cache.append(value)
>>      return cache[n]
>>
>> This one takes less than a millisecond up to n=200 or so.
>
> 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.

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.
-- 
DaveA