One of the first assignments frequently given to new programming
students is the Fibonacci function: given a number *n*,
return the *n**th* number in the
Fibonacci sequence. A typical response to this assignment might be coded as
follows:

def fib(n): if n == 0: return 0 elif n == 1: return 1 else: fib(n−1) + fib(n−2)

Unfortunately, this code has a trick: trying to compute
*fib(n)* any numbers larger than 40 or so results in
incredibly long running times. In algorithmic terms, this code has
complexity O(2^{n}). In other words, the running
time increases exponentially as the number requested goes up. Before
*n* gets very large, the running time is too long to be
feasible.

The reason why the fib function is so expensive is because it redoes
the work each time. If you ask for *fib(5)*, the function
also works out *fib(4)* and *fib(3)*.
The calculation of *fib(4)* in turn works out
*fib(3)* and *fib(2)*. The calculation
of *fib(3)* works out *fib(2)* and
*fib(1)*, etc. There is a lot of duplicated effort, and
that duplicated effort takes work and time.

One technique for speeding up this function is *memoization*. Memoization works by caching the results of each call in a lookup table. The first time a function is called with certain arguments, the memoized function computes the result and associates the function arguments with the result value. When the function is called later with the same arguments, the memoized function returns the cached value rather than spending time and processing power ...

Start Free Trial

No credit card required