Lycée Claude Fauriel MP2I
TRAVAUX PRATIQUES VIII
Récursivité en OCaml
On rappelle que les codes doivent être compilés avec ocamlopt et testés !
A Autour du cours
1. Écrire une fonction récursive factorielle qui prend en argument un entier n et calcule sa factorielle 𝑛!
(sans regarder dans le cours).
2. Ré-écrire la factorielle avec de la récursivité terminale (avec un accumulateur).
3. a. Écrire une fonction récursive ligne_etoiles : int -> unit qui prend en argument un entier n, s’éva-
lue à unit et a pour effet de bord d’afficher n caractères * . Vous pourrez réduire le problème d’afficher n
étoiles à celui d’afficher n-1 étoiles.
b. Écrire une fonction récursive triangle_bas : int -> unit qui affiche un triangle de base n pointe
vers le bas comme ceci pour n=4 :
* * * *
* * *
* *
*
c. Écrire une fonction récursive triangle_haut : int -> unit qui comme effet secondaire affiche un
triangle de base n pointe vers le haut comme ceci pour n=4 :
*
* *
* * *
* * * *
4. Écrire une fonction récursive somme_f : (int->int) -> int -> int qui prend en argument une fonction
𝑛
f : int->int et un entier positif n et qui caclule ∑ 𝑓(𝑖).
𝑖=0
5. Ré-écrire votre fonction somme_f en version récursive terminale.
B Manipulation des listes
6. Écrire une fonction somme_liste : int list -> int qui renvoie la somme des éléments d’une liste. Vous
utiliserez du filtrage.
7. Écrire une fonction max_liste : int list -> int qui renvoie le maximum des éléments d’une liste.
8. Ré-écrire votre fonction max_liste en version récursive terminale.
C Un peu de maths
C.1 Maths du supérieur
9. a. Les nombres de Catalan forment une suite d’entiers naturels définis par :
1
TP VIII. Récursivité en OCaml
2(2𝑛 + 1)
𝐶0 = 1, ∀𝑛 ≥ 1, 𝐶𝑛+1 = 𝐶𝑛
𝑛+2
Écrire une fonction catalan qui prend en argument un entier naturel 𝑛 et qui calcule 𝐶𝑛 .
b. Vérifier les valeurs des nombres de Catalan sur Internet pour vous assurer que votre fonction est correcte (il
y a des pièges !)
c. (Difficile) Modifier votre fonction pour qu’elle soit récursive terminale.
10. Récursivité croisée : Étant donnés deux réels 𝑎 et 𝑏, on définit les suites suivantes :
𝑎 si 𝑛 = 0 𝑏 si 𝑛 = 0
𝑢𝑛 = { 𝑢𝑛−1 +𝑣𝑛−1 𝑣𝑛 = {√
2 sinon 𝑢𝑛−1 ⋅ 𝑣𝑛−1 sinon
Écrire une fonction u : float -> float -> int -> float qui prend en argument a, b et n et calcule 𝑢𝑛 .
De même pour v .
C.2 Maths de primaire
Les mathématiques du supérieur, c’est bien. Mais l’école primaire, c’est mieux 1 !
11. a. Écrire une fonction prod : int -> int -> int qui prend en argument deux entiers positifs x et y et
calcule x*y sans utiliser * .
b. Écrire une fonction div : int -> int -> int qui prend en argument deux entiers positifs x et y et
renvoie x/y (division entière) sans utiliser / ni mod .
c. Écrire une fonction reste : int -> int -> int qui prend en argument deux entiers positifs x et y et
renvoie x mod y (le reste de x divisé par y) sans utiliser / ni mod .
D Impératif contre récursif
12. Définir une fonction récursive repete qui prend en arguments une fonction f et un entier n et qui renvoie
la fonction f appliquée n fois : 𝑓𝑜𝑓𝑜...𝑜𝑓 (en mathématiques, on écrit parfois 𝑓 𝑛 quand ce n’est pas ambigu).
13. Même question mais en programmation impérative (avec une boucle).
E Pour occuper les plus rapides
14. Écrire une fonction parties : int list -> int list list qui prend en argument un ensemble S sous
forme d’une liste et renvoie l’ensemble de toutes les parties de S, peu importe l’ordre.
Exemple : si S = [1 ;2 ;3] alors (parties S) est [[] ; [1] ; [2] ; [3] ; [1 ;2] ; [1 ;3] ; [2 ;3] ; [1 ;2 ;3]].
15. a. Écrire une fonction isole : int -> 'a list -> 'a list telle que isole n lst renvoie les n
premiers éléments de lst. Si lst contient moins de n éléments, elle les renvoie tous.
b. Écrire une fonction enleve : int -> 'a list -> 'a list telle que enleve n lst renvoie la liste
lst privée de ses n premiers éléments. Si lst contient moins de n éléments, elle renvoie une liste vide.
16. a. Écrire une fonction qui prend un entier en argument et teste si son écriture en base 10 est un palindrome ou
non.
b. L’adapter pour qu’il prenne une base 𝑏 en argument et teste si l’écriture en base 𝑏 est palindromique.
1. Et c’est un peu plus de l’informatique.