OCaml (option informatique) · Chapitre 1 · Exercice de TD

Suite définie par récurrence mutuelle

Découvrir OCaml : expressions, valeurs et types · niveau 3 (difficile)

Énoncé

On définit deux suites par $u_{0} = 1$ , $v_{0} = 1$ , et pour $n \geq 1$ : $u_{n} = u_{n - 1} + v_{n - 1}$ , $v_{n} = u_{n - 1}$ . Écrire u et v (de type int -> int). Que reconnaît-on ?

Corrigé

let rec u n =
  if n = 0 then 1 else u (n - 1) + v (n - 1)
and v n =
  if n = 0 then 1 else u (n - 1)

Comme $v_{n} = u_{n - 1}$ , on a $u_{n} = u_{n - 1} + u_{n - 2}$ : on reconnaît la suite de Fibonacci (décalée). Le let rec ... and ... est ici indispensable, car u et v se référencent mutuellement. (Cette définition recalcule énormément ; on apprendra plus tard à l'accélérer.)

Exercices semblables

Application partielle corrigé
Fonction d'ordre supérieur et polymorphisme corrigé
Manipuler des n-uplets corrigé
L'algorithme d'Euclide corrigé
Puissance entière et dépassement corrigé

Le cours du chapitre · Tous les exercices du chapitre