# Scheme Programming/Memoisation

Jump to navigation
Jump to search

Memoization is a programming technique that allows programs to remember the results of prior computations. This technique has numerous benefits; here we will address its use in speeding up certain algorithms.

For example, the following program to compute Fibonacci numbers is correct, but slow:

```
(define fibonacci
(lambda (n)
(cond
((or (= n 1) (= n 2)) 1)
(else (+ (fibonacci (- n 1)) (fibonacci (- n 2)))))))
```

Those with some understanding of analysis of algorithms will note that each call to (fibonacci n) for n > 2 requires two more calls of the fibonacci function, so the algorithm has a worst case running time of O(2^{n}). We can clearly do better. Observe that (fibonacci 1000) takes quite a while to compute, and may even crash your interpreter if it runs out of memory.