16.7: Memorized Fibonacci

As a small application of the techniques we have seen, consider the Fibonacci function (\( \mathit{fib}(n) = \mathit{fib}(n - 1) + \mathit{fib}(n - 2) \text{ with } \mathit{fib}(0) = 0, \mathit{fib}(1) = 1 \)). We will study two versions of it: a recursive version and a memorized version. Memoizing consists in introducing a cache to avoid redundant computation.

Consider the following definition, close to the mathematical definition:

Integer»fibSlow
    self assert: self >= 0.
    (self <= 1) ifTrue: [ ^ self].
    ^ (self - 1) fibSlow + (self - 2) fibSlow

The method fibSlow is relatively inefficient. Each recursion implies a duplication of the computation. The same result is computed twice, by each branch of the recursion.

A more efficient (but also slightly more complicated) version is obtained by using a cache that keeps intermediary computed values. The advantage is to not duplicate computations since each value is computed once. This classical way of optimizing program is called memoizing.

Integer»fib
    ^ self fibWithCache: (Array new: self)

Integer»fibLookup: cache
    | res |
    res := cache at: (self + 1).
    ^ res ifNil: [ cache at: (self + 1) put: (self fibWithCache: cache ) ]

Integer»fibWithCache: cache
    (self <= 1) ifTrue: [ ^ self].
    ^ ((self - 1) fibLookup: cache) + ((self - 2) fibLookup: cache)

As an exercise, profile 35 fibSlow and 35 fib to be convinced of the gain of memoizing.

---