Une mémoïsation qui ne mémoïse rien

let rec fib n =
  let memo = Hashtbl.create 97 in
  let rec aux k =
    if k < 2 then k
    else match Hashtbl.find_opt memo k with
      | Some v -> v
      | None ->
          let v = fib (k - 1) + fib (k - 2) in     (* <-- ici *)
          Hashtbl.add memo k v;
          v
  in
  aux n

La faute tient en trois lettres : le corps appelle fib au lieu de aux. Or fib recrée une table vide à chaque appel. Chaque sous-appel repart donc d'une mémoire neuve, et aucune valeur n'est jamais retrouvée : la table est écrite, jamais lue.

Mesure (compteur d'appels à aux) :

n=10  fib=   55  appels = 177      (naif : 177)
n=20  fib= 6765  appels = 21891    (naif : 21891)
n=25  fib=75025  appels = 242785   (naif : 242785)

Exactement le nombre d'appels de la version naïve — la mémoïsation coûte le prix d'une table de hachage par appel, et ne rapporte rien. Le programme est même plus lent que le naïf.

Comment on l'attrape. Pas en lisant : en mesurant. Une mémoïsation correcte doit faire chuter le nombre d'appels d'un ordre de grandeur ; un compteur temporaire, ou un simple chronomètre sur $n=35$, distingue les deux versions en une seconde. C'est le point du chapitre chap:discipline : un test qui n'observe que la valeur de retour ne voit pas cette faute, puisque le résultat est juste.

La correction est d'écrire aux (k - 1) + aux (k - 2), et l'on peut alors retirer le rec sur fib : le compilateur signale alors la faute tout seul si elle revient. Retirer un rec inutile n'est pas de la coquetterie : c'est transformer une faute silencieuse en erreur de compilation.