Caml Light

Fonction factorielle

Pour des entiers naturels, la fonction factorielle est définie par :

${\displaystyle n!=\prod _{i=1}^{n}i=1\times 2\times 3\times \cdots \times (n-1)\times n}$

et sa définition récursive est :

${\displaystyle n!={\begin{cases}1\quad {\mbox{si }}n=0\\n\times (n-1)!\quad {\mbox{ sinon}}\end{cases}}}$

En Caml Light, cela donne :

let rec fact = function
  | 0 -> 1
  | n -> n * fact (n - 1);;

Algorithme d'Euclide

L'algorithme d'Euclide, pour calculer le pgcd de deux entiers naturels u, v, s'écrit en Caml Light

let rec pgcd u v = 
  if u = 0 then v
  else pgcd (v mod u) u;;

Suite de Fibonacci

La suite de Fibonacci ${\displaystyle (F_{n})_{n\geq 1}}$ est définie par :

${\displaystyle F_{0}=0,F_{1}=1,\quad F_{n+2}=F_{n+1}+F_{n}\quad {\mbox{ avec }}n\geq 0}$

.

En Caml Light on a la version récursive naïve, qui s'exécute en temps exponentiel :

let rec fibonacci n =
  match n with
    | 0 -> 0
    | 1 -> 1
    | _ -> fibonacci (n - 1) + fibonacci (n - 2) ;;

let f = fibonacci 9 ;;

ou encore, en version récursive terminale prenant en argument les deux premiers termes ${\displaystyle a}$ et ${\displaystyle b}$ et s'exécutant en temps linéaire :

let rec fibonacci n a b =
  match n with
    | 0 -> a
    | 1 -> b
    | _ -> fibonacci (n - 1) b (a + b) ;;

let f = fibonacci 9 0 1 ;;

On combine couramment les deux, pour disposer à l’extérieur d’une fonction simple, et à l’intérieur de la récursion terminale :

let fibonacci n =
  (* Définir la version récursive avec récursion terminale… *)
  let rec fib_2termes n a b =
    match n with
    | 0 -> a
    | 1 -> b
    | _ -> fib_2termes (n - 1) b (a + b)
  (* … et l’utiliser. *)
  in fib_2termes n 0 1 ;;

let f = fibonacci 9 ;;

On dispose aussi de deux versions itératives s'exécutant en temps linéaire (${\displaystyle O(n)}$), la première en espace linéaire et la seconde en espace constant :

let fibonacci n =
  (* Un vecteur (tableau) de n+1 éléments entiers initialisés à 1. *)
  let t = make_vect (n + 1) 1 in
  (* Calculer ce vecteur pour les éléments n° 2 à n. *)
  for k = 2 to n do
    t.(k) <- t.(k - 1) + t.(k - 2)
  done;
  (* Le résultat est dans le dernier élément du vecteur. *)
  t.(n);;

let f = fibonacci 9 ;;

let fibonacci n =
  (* 3 variables modifiables (refs) n1, n2, aux. *)
  let n1 = ref 1 in
  let n2 = ref 1 in
  let aux = ref 1 in
  (* Recalculer itérativement ces variables jusqu’à n. *)
  (* Syntaxe: !x dénote l’accès à la valeur actuelle de x. *)
  for k = 2 to n do
    aux := !n1;
    n1 := !n2;
    n2 := !n2 + !aux;
  done;
  (* Le résultat est dans n2. *)
  !y;;

let f = fibonacci 9 ;;