Memoization is a concept based on lazy evaluation and caching of function results. If you have a function without side effects and you call the function multiple times with the same arguments, then it is sufficient to call the function only once and use the result multiple times.

Of course this concept has some disadvantages. You have to store the function results in a lookup table which needs space and the table lookups take time. But in a lot of cases these disadvantages are ignorable compared with the big advantages of this memorization concept.

I want to explain the idea by using the Fibonacci calculation example. The Fibonacci number is the sum of the previous two Fibonacci numbers where the first two results are “1”. This means the first Fibonacci number is “1”, the second is also “1”, the third is “2” (1+1), the forth is “3” (1+2), the fifth is “5” (2+3) and so on.

This function may be implemented by using recursion. The following source code shows an according example of a basic Fibonacci function.

let rec fibonnaci_simple x = 
    match x with
    | 1 -> 1
    | 2 -> 1
    | x -> fibonnaci_simple(x-1) + fibonnaci_simple(x-2)

 
But this simple implementation has on big disadvantage: the execution time will grow exponentially. You may test this by using “30”, “40” and “50” as parameter. The execution time will grow that fast because for each calculation of a Fibonacci number the two previous numbers must be calculated. And if the two previous numbers should be calculated their previous numbers are needed. Therefore the same numbers will be calculated several times.

But of course it is possible to optimize the calculation function. I want to show you two possible solutions. The first solution is made for this special Fibonacci use case and the second example shows a general solution which may be used in a lot of different use cases.

 
Count up

An even very simple but resource friendly and fast solution of the Fibonacci calculation is to calculate the value by counting up. In this case you have to start by one and count up the sum of the values until the target parameter is reached. The Seq.unfold function may be used to implement this solution. The following source code shows an according example. By using Seq.unfold the partial results will be calculated as result of the sum of the two previous values. This will be done until the given number of sequence members is reached and the last sequence member will be returned as final result.

let fibonnaci_count_up n = 
    let create_sequence = 
        Seq.unfold (fun (x,y) -> Some(x,(y,x+y))) (1,1)

    Seq.nth (n-1) create_sequence

 
Memoization

By using the concept of Memoization, a more generic solution can be implemented. Of course the next solution is also implemented to solve the Fibonacci calculation but the concept may be easily adapted for other use cases.

The following source code shows an extended version of the first solution. An additional Array is used to store the results of the function calls. These cached results will be used instead of calling the function multiple times with the same parameter.

let rec fibonnaci_memoization x = 
    let results = Array.create x 0

    let rec fibonnaci_memoization_internal y =
        if results.[y-1] <> 0 then
            results.[y-1]
        else
            match y with
            | 1 -> 
                results.[y-1] <- 1
                1
            | 2 -> 
                results.[y-2] <- 1
                1
            | y -> 
                results.[y-2] <- fibonnaci_memoization_internal(y-1)
                results.[y-3] <- fibonnaci_memoization_internal(y-2)
                results.[y-2] + results.[y-3]

    fibonnaci_memoization_internal x

 
Summary

Whenever a recursive function calls itself multiple time with the same parameters you may think about an optimization of the function by using the concepts of Memoization. Of course such an optimization is not needed every time. But if it is necessary the concept of Memoization will offer you an easy to implement solution.