(* Calcul de fib(n) itérativement, en conservant seulement les deux
   dernières valeurs *)

let fib n =
  let rec fib_aux a b i = (* invariant : a = fib(i) et b = fib(i+1) *)
    if i = n then a else fib_aux b (a + b) (i + 1)
  in
  fib_aux 0 1 0

(* note : on va un cran plus loin que nécessaire, ce qu'on peut éviter
   en traitant à part le cas n = 0 *)

let () =
  assert (fib 0 = 0);
  assert (fib 1 = 1);
  assert (fib 10 = 55);
  assert (fib 14 = 377)

This document was generated using caml2html