# Recursion and Memoization

12 Apr 2014To iterate is human, to recurse divine.

~ L. Peter Deutsch

Recursion is available in many high-level languages, including Ruby. Recursive solutions can be joyfully elegant. At the same time, the pursuit of elegance can lead to unexpected performance pitfalls.

Fortunately, we can use optimization techniques to address performance problems before they occur. Memoization is one technique in our arsenal.

### Before Memoization

Memoization was designed to solve a particular kind of problem. Consider a method called `fibo(n)`

that calculates the *nth* number of the Fibonacci sequence.

```
# Calculate the nth Fibonacci number, f(n).
def fibo (n)
if n <= 1
return n
else
value = fibo(n-1) + fibo(n-2)
return value
end
end
# Display the Fibonacci sequence.
(1..40).each do |number|
puts "fibo(#{number}) = #{fibo(number)}"
end
```

The example runs, but performance slows down as *n* gets larger. Why? Because this method re-calculates all preceeding Fibonacci numbers every time it calculates a new `fibo(n)`

. When we calculate Fibonacci numbers manually, we know better. Humans are smart enough to refer to earlier work. But the `fibo(n)`

method does not manage time very well.

Is it possible for the `fibo(n)`

method to remember the results of earlier calculations so that it can avoid doing work that is already done? Yes, through memoization.

### Memoization

Memoization means recording the results of earlier calculations so that we don’t have to repeat the calculations later. If our code depends on the results of earlier calculations, and if the same calculations are performed over-and-over again, then it makes sense to store interim results (jot results down on a ‘memo’ = memoization) so that we can avoid repeating the math.

The Fibonacci example can be improved through memoization as follows.

- Create a place to store temporary results.
- Before performing a calculation, find out if the calculation has already been done. If so, use the stored result.
- If this is our first time calculating a particular
`fibo(n)`

, store the results for future use.

Here’s how memoization is implemented in the Fibonacci example:

```
# Fibonacci numbers WITH memoization.
# Initialize the memoization array.
@scratchpad = []
@max_fibo_size = 50
(1..@max_fibo_size).each do |i|
@scratchpad[i] = :notcalculated
end
# Calculate the nth Fibonacci number, f(n).
def fibo (n)
if n > @max_fibo_size
return "n must be #{@max_fibo_size} or less."
elsif n <= 1
return n
elsif @scratchpad[n] != :notcalculated
return @scratchpad[n]
else
@scratchpad[n] = fibo(n-1) + fibo(n-2)
return @scratchpad[n]
end
end
# Display the Fibonacci sequence.
(1..50).each do |number|
puts "fibo(#{number}) = #{fibo(number)}"
end
```

Walking through the code… First we create a memoization array, a place to store the pre-calculated values. In this example, `@scratchpad[]`

serves as our memoization array.

The `fibo(n)`

method is similar to the one in the earlier example, with a few subtle differences. First, we need to determine whether we’ve already calculated a particular value. Since we initialized all elements of the `@scratchpad`

array with the `:notcalculated`

symbol, it’s easy to figure out where work needs to be done. If a Fibonacci number `fibo(n)`

has already been calculated, we return the value stored at `@scratchpad[n]`

. Otherwise, we calculate the new `fibo(n)`

and store that value at `@scratchpad[n]`

for later use.

### Performance Comparison

The performance of the two programs is compared in this 1-minute video.

As the video shows, memoization is a performance booster.

### Sample Code

Sample code related to this article can be found on GitHub.