Chapter 10if n == 0: return 0
if n == 1: return 1
return fibc(n-1) + fibc(n-2)
This is an example based on Chapter 6, Recursions and Reductions. We've applied the
@lru_cache decorator to the naïve Fibonacci number calculation. Because of this
decoration, each call to the fibc(n) function will now be checked against a cache
maintained by the decorator. If the argument, n, is in the cache, the previously
computed result is used instead of doing a potentially expensive re-calculation.
Each return value is added to the cache. When the cache is full, the oldest value is
ejected to make room for a new value.
We highlight this example because the naïve recursion is quite expensive in this case.
The complexity of computing any given Fibonacci number, Fn, involves not merely
computing Fn− 1 but Fn− 2 also. This tree of values leads to a complexity in the order
of O() 2 n.
We can try to confirm the benefits empirically using the timeit module. We can
execute the two implementations a thousand times each to see how the timing
compares. Using the fib(20) and fibc(20) methods shows just how costly this
calculation is without the benefit of caching. Because the naïve version is so slow,
the timeit number of repetitions was reduced to only 1,000. Following are the results:
- Naive 3.23
- Cached 0.0779
Note that we can't trivially use the timeit module on the fibc() function. The
cached values will remain in place: we'll only compute the fibc(20) function once,
which populates this value in the cache. Each of the remaining 999 iterations will
simply fetch the value from the cache. We need to actually clear the cache between
uses of the fibc() function or the time drops to almost 0. This is done with a fibc.
cache_clear() method built by the decorator.
The concept of memoization is powerful. There are many algorithms that can benefit
from memoization of results. There are also some algorithms that might not benefit
quite so much.
The number of combinations of p things taken in groups of r is often stated as follows:
()!
!!p p
r rp r
=
−