fibonacci series what Iam is missing ?
Terry Reedy
tjreedy at udel.edu
Mon Mar 23 21:45:25 EDT 2015
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
More information about the Python-list
mailing list