Using the previous example of calculating the factorial of an integer, put in the hash table all values of factorial calculated inside the recursion, that do not appear in the table.
As in the article about memoization, we declare a function f that accepts a function parameter fact and a integer parameter. This function f, includes instructions to calculate the factorial of n from fact(n-1).
This allows to handle recursion by the function returned by memorec and not by fact itself and possibly stop the calculation if the fact(n-1) value has been already calculated and is located in the hash table.
Memoization consists of caching function results to avoid computing the same result multiple times. This is useful when working with functions that perform costly computations.
We can use a simple factorial function as an example:
Calling this function multiple times with the same parameter results in the same computation again and again.
Memoization will help us to cache the factorial result and return it if the same parameter is passed again.
Here is a simple memoization implementation :
The memoization function simply takes a function as a parameter and returns a function with the same signature. You could see this in the method signature f:('a -> 'b) -> ('a -> 'b). This way you can use memoization the same way as if you were calling the factorial method.
The printfn calls are to show what happens when we call the function multiple times; they can be removed safely.
Using memoization is easy:
This modified text is an extract of the original Stack Overflow Documentation created by following contributors and released under CC BY-SA 3.0