Fibonacci itératif

Exercice · OCaml (option informatique), chapitre 4 — Programmation impérative : références et boucles

Énoncé

Écrire fibo n ( $n \geq 0$ ) en $Θ (n)$ avec deux références, et expliquer l'avantage sur la version doublement récursive du chapitre 3.

Corrigé

let fibo n =
  let a = ref 0 and b = ref 1 in
  for _i = 1 to n do
    let s = !a + !b in
    a := !b;
    b := s
  done;
  !a

On fait avancer une « fenêtre » de deux termes consécutifs. fibo 0 $= 0$ , fibo 1 $= 1$ , fibo 6 $= 8$ . Coût $Θ (n)$ : chaque terme est calculé une fois, là où la définition récursive naïve $u_{n} = u_{n - 1} + u_{n - 2}$ recalcule exponentiellement les mêmes valeurs.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.