Mémoïsation de Fibonacci

let memo = Hashtbl.create 100

let rec fibo n =
  if n < 2 then n
  else
    match Hashtbl.find_opt memo n with
    | Some v -> v
    | None ->
        let v = fibo (n - 1) + fibo (n - 2) in
        Hashtbl.add memo n v;
        v

Avant de calculer fibo n, on regarde s'il est déjà en cache. Sinon on le calcule une fois et on l'enregistre. Chaque valeur n'est ainsi calculée qu'une fois : on passe du coût exponentiel de la version naïve (chapitre 3) à un coût linéaire. C'est la mémoïsation — la programmation dynamique appliquée par cache.