fibonacci series what Iam is missing ?

[Terry Reedy]

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.

-- 
Terry Jan Reedy