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 la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, des Quiz (plus de 600 questions), etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (6 mois), 25€ (1 an) ou 35€ (2 ans).

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 la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, des Quiz (plus de 600 questions), etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (6 mois), 25€ (1 an) ou 35€ (2 ans).

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

Cliquer ici pour voir (ou cacher) le corrigé
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, des Quiz (plus de 600 questions), etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (6 mois), 25€ (1 an) ou 35€ (2 ans).

Exercice 4.
Deviner ce que fait la fonction « hop » :

Cliquer ici pour voir (ou cacher) le corrigé
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, des Quiz (plus de 600 questions), etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (6 mois), 25€ (1 an) ou 35€ (2 ans).

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 la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, des Quiz (plus de 600 questions), etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (6 mois), 25€ (1 an) ou 35€ (2 ans).

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 la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, des Quiz (plus de 600 questions), etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (6 mois), 25€ (1 an) ou 35€ (2 ans).

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 la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, des Quiz (plus de 600 questions), etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (6 mois), 25€ (1 an) ou 35€ (2 ans).

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 la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, des Quiz (plus de 600 questions), etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (6 mois), 25€ (1 an) ou 35€ (2 ans).

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 la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, des Quiz (plus de 600 questions), etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (6 mois), 25€ (1 an) ou 35€ (2 ans).

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

Cliquer ici pour voir (ou cacher) le corrigé
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, des Quiz (plus de 600 questions), etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (6 mois), 25€ (1 an) ou 35€ (2 ans).

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

Cliquer ici pour voir (ou cacher) le corrigé
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, des Quiz (plus de 600 questions), etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (6 mois), 25€ (1 an) ou 35€ (2 ans).

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 la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, des Quiz (plus de 600 questions), etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (6 mois), 25€ (1 an) ou 35€ (2 ans).

Author: Jean-Michel Ferrard

Professeur de mathématiques en classe préparatoire aux grandes écoles.