memoize_rec.fs

open System

let memo_rec f =
  let m = ref Map.empty in
  let rec g x =
    match Map.tryFind x !m with
    | Some ans -> ans
    | None ->
        let y = f g x in
        m := Map.add x y !m
        y
  in
  g

let fib =
  let rec f self = function
    | 0 -> 0L
    | 1 -> 1L
    | 2 -> 1L
    | i ->
        let p1 = self (i-1) in
        let p2 = self (i-2) in
        p1 + p2
  in
  memo_rec f