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
--
https://mail.python.org/mailman/listinfo/python-list
