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