Jupyter at Bryn Mawr College
Public notebooks: /services/public/dblank / CS245 Programming Languages / 2014-Fall / Notes

Fibonacci, recursion, and memoization in Scheme

We examined the running speed of computing the $n^{th}$ Fibonacci number in Scheme.

In [1]:
(define fib
  (lambda (n)
    (if (or (= n 1)
            (= n 2))
        1
        (+ (fib (- n 1))
           (fib (- n 2))))))
In [2]:
(map fib (range 1 11))
Out[2]:
(1 1 2 3 5 8 13 21 34 55)

How much time does it take to compute?

In [3]:
%%time
(fib 10)

Time: 0.102875947952 seconds.
Out[3]:
55
In [4]:
%%time
(fib 20)

Time: 11.850864172 seconds.
Out[4]:
6765
In [5]:
(import-as "calico.widgets" '*)
(import-as "calico.display" 'display)

(GoogleChart "LineChart" '("n" "Time")
    (map (lambda (n)
           (let ((start (current-time)))
             (fib n)
             (- (current-time) start)))
         (range 1 20)))
Out[5]:
In [6]:
(define count 0)
(define counter
   (lambda (f)
     (lambda (n)
       (set! count (+ count 1))
       (f n))))
In [7]:
(define fib (counter fib))
In [8]:
(define test-fib
  (lambda (n)
    (set! count 0)
    (fib n)
    count))
In [9]:
(GoogleChart "LineChart" '("n" "Count")
    (map (lambda (n)
           (test-fib n))
         (range 1 20)))
Out[9]:

Wow... that does take some time to compute as n get just slightly larger!

Is it because recursion is bad? No, not at all.

Instead of recomputing the same values over and over, perhaps we should save them?

Here is a technique called memoization (related to Dynamic Programming). We can take any function and wrap this around it. It then acts as an intermediary... if the value is in its cache, then we retrieve it from there. Otherwise we compute it and save it.

In [10]:
(define memoize
  (lambda (f)
    (let ((cache (dict)))
        (lambda (n)
          (if (contains cache n)
              (getitem cache n)
              (setitem cache n (f n)))))))

Now, we wrap fib:

In [22]:
(define fib
  (lambda (n)
    (if (or (= n 1)
            (= n 2))
        1
        (+ (fib (- n 1))
           (fib (- n 2))))))

First we apply memoization:

In [23]:
(define fib (memoize fib))

Then we apply the counter on top:

In [24]:
(define fib (counter fib))
In [25]:
(GoogleChart "LineChart" '("n" "Count")
    (map (lambda (n)
           (test-fib n))
         (range 1 20)))
Out[25]:
In [19]:
%%time
(fib 10)

Time: 0.0459508895874 seconds.
Out[19]:
55
In [20]:
%%time
(fib 20)

Time: 0.0506360530853 seconds.
Out[20]:
6765

Wow... that is some speed up! Why does it appear to be constant of 3 calls for each fib we compute? Let's do it again.

In [26]:
(GoogleChart "LineChart" '("n" "Count")
    (map (lambda (n)
           (test-fib n))
         (range 1 20)))
Out[26]:

Now it is a contant of 1 call for each we fib compute.

What is the Big O of Fib without memoization? It is bounded by:

$\dfrac{1}{\sqrt{5}} 1.618^{n+1}$

which is $O(2^n)$.

http://courses.csail.mit.edu/6.01/spring07/lectures/lecture4.pdf

In [32]:
(import "math")

(define f_hat
  (lambda (n)
    (* (/ 1 (math.sqrt 5)) (math.pow 1.618 (+ n 1)))))

How many times is fib called in (fib 20).

In [34]:
(f_hat 20)
Out[34]:
10941.172384126632