OCaml. Exercices sur la récursivité

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}.
Cliquer ici pour voir (ou cacher) le corrigé
  Pour voir ce contenu, vous devez : 

Exercice 2.
Devinez ce que font les fonctions suivantes, dont l’argument {n} est supposé positif ou nul.

Cliquer ici pour voir (ou cacher) le corrigé
  Pour voir ce contenu, vous devez : 

Exercice 3.
Deviner le type de la fonction “what”, et ce qu’elle fait :

Cliquer ici pour voir (ou cacher) le corrigé
  Pour voir ce contenu, vous devez : 

Exercice 4.
Deviner ce que fait la fonction “hop” :

Cliquer ici pour voir (ou cacher) le corrigé
  Pour voir ce contenu, vous devez : 

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}.
Cliquer ici pour voir (ou cacher) le corrigé
  Pour voir ce contenu, vous devez : 

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).
Cliquer ici pour voir (ou cacher) le corrigé
  Pour voir ce contenu, vous devez : 

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}.
Cliquer ici pour voir (ou cacher) le corrigé
  Pour voir ce contenu, vous devez : 

Exercice 8.
Écrire une fonction “hanoi : int -> unit” résolvant le problème des tours de Hanoï.
Cliquer ici pour voir (ou cacher) le corrigé
  Pour voir ce contenu, vous devez : 

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.
Cliquer ici pour voir (ou cacher) le corrigé
  Pour voir ce contenu, vous devez : 

Exercice 10.
Que font les fonctions {f} et {g}?

Cliquer ici pour voir (ou cacher) le corrigé
  Pour voir ce contenu, vous devez : 

Exercice 11.
Que font les fonctions {f} et {g}?

Cliquer ici pour voir (ou cacher) le corrigé
  Pour voir ce contenu, vous devez : 

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}.
Cliquer ici pour voir (ou cacher) le corrigé
  Pour voir ce contenu, vous devez :