Memoization of recursive functions

fibonacciRecursiveMemoization.fs

// Example 7-20. Memoization of recursive functions
> // WRONG way to memoize the function - fib doesn't call the
// memoized version recursively.
let wrongMemFib =
let rec fib x =
match x with
| 0 | 1 -> 1
| 2 -> 2
| n -> fib (n - 1) + fib (n - 2)
memoize fib;;
val wrongMemFib : (int -> int)
> // CORRECT way to memoize the function - fib does call
// the memoized version recursively.
let rec rightMemFib =
let fib x =
match x with
| 0 | 1 -> 1
| 2 -> 2
| n -> rightMemFib (n - 1) + rightMemFib (n - 2)
memoize fib;;
val rightMemFib : (int -> int)
> #time;;
--> Timing now on
> wrongMemFib 45;;
Real: 00:00:21.553, CPU: 00:00:21.528, GC gen0: 0, gen1: 0, gen2: 0
val it : int = 1836311903
> rightMemFib 45;;
Real: 00:00:00.001, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val it : int = 1836311903