Exercice 1.
Les nombres de Catalan satisfont à : {c_0=1} et à la relation {c_n=\dfrac{2(2n-1)}{n+1}c_{n-1}} pour tout {n\ge 1}.
Écrire une fonction récursive « catalan : int -> int » renvoyant {c_n}.
Exercice 5.
Écrire une fonction « add : int -> int -> int », récursive terminale, et effectuant la somme de ses deux arguments (supposés {\ge0}). Les seules opérations autorisées sont l’addition ou la soustraction de {1}.
Exercice 6.
Écrire une fonction « mul : int -> int -> int », utilisant une fonction auxiliaire récursive terminale, et effectuant le produit de ses deux arguments (supposés {\ge0}). Les seules opérations autorisées sont l’addition, et la multiplication par 2 (ou la division par 2 d’un nombre pair).
Exercice 7.
Écrire une fonction « itere : int -> (‘a -> ‘a) -> ‘a -> ‘a » calculant la valeur en un point {x} de la {n}-ième itérée {f\circ f\ldots\circ f} d’une fonction {f} définie sur (et à valeurs dans) le type de {x}.
Exercice 9.
On définit la suite de Syracuse par {u_{0}=a} et {\forall\, n\in\mathbb{N}} : {u_{n+1}=u_{n}/2} si {n} est pair et {u_{n+1}=3n+1} si {n} est impair.
Écrire une fonction #{syracuse : int -> int list} renvoyant la liste formée de l’orbite (jusqu’à ce qu’on obtienne {u_{n}=1}) d’un entier {a} donné dans la suite de Syracuse.
Exercice 12.
Écrire une fonction « somme : (int -> int) * int * int * int -> int » prenant en argument un quadruplet {(f,a,b,h)} et calculant la somme des {f(n)} pour {n} allant de {a} à {b} avec un pas de {h}.