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