Suite définie par récurrence mutuelle

Exercice · OCaml (option informatique), chapitre 1 — Découvrir OCaml : expressions, valeurs et types

É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.)

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.