C5 Récursivité ¶

"In order to understand recursion, one must first understand recursion. "
Anonyme

Cours¶

Attention

Ce diaporama ne vous donne que quelques points de repères lors de vos révisions. Il devrait être complété par la relecture attentive de vos propres notes de cours et par une révision approfondie des exercices.

Travaux dirigés¶

Fiche de TD5

Travaux pratiques¶

Note

Pour les exercices qui suivent, lorsque cela est possible (donc lorsqu'on ne traite pas de tableaux), on pourra proposer une implémentation en OCaml en s'inspirant des exemples vus en cours.

Exercice 1 : Somme des éléments d'un tableau¶

Écrire une fonction itérative somme_iter qui prend en argument un tableau d'entiers et sa taille \(n\) et renvoie la somme des éléments de ce tableau.
On note \(S(n)\) la somme des éléments du tableau jusqu'à l'indice \(n\). Écrire une relation de récurrence entre \(S(n)\) et \(S(n-1)\).
Donner une version récursive de la fonction somme.
Écrire une fonction récursive terminale.

Aide

Pour cet exercice, on pourra s'inspirer de la fonction factorielle vue en cours et dont on donne les différentes versions ci-dessous :

 int fact_iter( int n){
     int res = 1;
    for ( int i=1;i<=n;i++){
        res = res * i;}
    return res;}

 int fact_rec( int n){
    if (n==0)
        {return 1;}
    return n*fact_rec(n-1);}

 int fact_acc( int n,  int acc){
    if (n==0)
        {return acc;}
    return fact_acc(n-1,n*acc);}

Exercice 2 : Château de cartes¶

Un château de cartes est un échafaudage de cartes à jouer. On a représenté ci-dessous des châteaux de cartes à 1, 2 et 3 étages (crédit : DREAMaths):

château de cartes

On note \(c_n\) le nombre de cartes nécessaires pour construire un château de cartes à \(n\) étages. Établir une relation de récurrence entre \(c_n\) et \(c_{n-1}\).
Écrire (dans le langage de votre choix) une fonction récurrente qui renvoie \(c_n\) pour la valeur \(n\) fournie en argument.
Calculer \(c_{100}\) à l'aide de votre programme. Vous pouvez vérifier le résultat fourni par votre programme ci-dessous :
Retrouver ce résultat par le calcul.

Exercice 3 : Additions et soustractions¶

On suppose qu'on ne dispose que de deux opérations : ajouter 1 ou retrancher 1.

Écrire à l'aide de ces deux opérations, une version itérative de l'addition de deux entiers.
Même question avec une version récursive.

Exercice 4 : Maximum récursif¶

Écrire une fonction max2 qui prend en argument deux entiers et renvoie le maximum de ces deux entiers.
Écrire une fonction récursive maximum qui prend en argument un tableau d'entiers (et sa taille) et renvoie le maximum des éléments de ce tableau.

Exercice 5 : Retourner une chaîne de caractères¶

Écrire une fonction retourne qui prend en argument une chaîne de caractères s et renvoie une chaîne de caractères contenant s écrite à l'envers. Par exemple si char test[]="Bonjour", alors retourne(s) renvoie la chaîne ruojnoB.
On décompose une chaîne en chaîne = début + dernier caractère, compléter la définition récursive suivante : envers(chaîne) = .......... + envers(.......)
En déduire une version récursive de la fonction envers.

Aide

On pourra écrire au préalable une fonction debut(chaine) qui renvoie la chaîne privée de son dernier caractère.

Exercice 6 : Algorithme d'Euclide de calcul du pgcd¶

Revoir si besoin l'algorithme d'Euclide permettant de calculer le pgcd de deux entiers.
Donner une implémentation itérative de cet algorithme.
Donner une implémentation récursive de cet algorithme.

Exercice 7 : Recherche dichotomique dans un tableau trié¶

L'algorithme de recherche dichotomique, s'applique lorsque le tableau est trié, il consiste à comparer l'élément cherché avec celui situé au milieu du tableau. Si la comparaison est infructueuse, on relance la recherche dans la moitié de tableau pertinente, ainsi à chaque étape, la taille de la zone de recherche est divisée par deux.

Par exemple, si on recherche \(\textcolor{red}{28}\) dans \([14, 15, 17, 22, 23, 25, 29, 34, 38]\), le tableau ci-dessous représente les étapes de la méthode :

Zone de recherche	Milieu	Comparaison
\(\underbrace{[\overset{\textcolor{red}{_\wedge^{0}}}{14}, 15, 17, 22,}_{ } \underset{_4^\uparrow}{\textcolor{darkblue}{23}} , \overbrace{25, 29, 34, \underset{\textcolor{red}{_8^{\vee}}}{38}]}_{ }\)	\((0+8)/2 = 4\)	\(\textcolor{darkblue}{23} <\textcolor{red}{28}\)
\([\colorbox{lightgray}{14, 15, 17, 22,23} , \underbrace{\overset{\textcolor{red}{_\wedge^{5}}}{25}} \underset{_6^\uparrow}{\textcolor{darkblue}{29}}, \overbrace{34, \underset{\textcolor{red}{_8^{\vee}}}{38}]}_{ }\)	\((5+8)/2=6\)	\(\textcolor{darkblue}{29} \geq \textcolor{red}{28}\).
\([\colorbox{lightgray}{14, 15, 17, 22,23} , \underset{_5^\uparrow}{\overset{\textcolor{red}{_\wedge^{5}}}{25}}, \underset{\textcolor{red}{_6^{\vee}}}{29} \colorbox{lightgray}{34,38}]\)	\((5+6)/2=5\)	\(\textcolor{darkblue}{25} < \textcolor{red}{28}\).
\([\colorbox{lightgray}{14, 15, 17, 22,23,25} \underset{\textcolor{red}{_6^{\vee}}}{\overset{\textcolor{red}{_\wedge^6}}{29}} \colorbox{lightgray}{34,38}]\)	-	-

Arrêt de l'algorithme, \(28\) n'est pas dans la liste.

Écrire en langage C une implémentation récursive de cet algorithme sous la forme d'une fonction de signature int dichotomie(int tab[], int v, int debut, int fin) qui recherche dans le tableau tab, la valeur v en se limitant à la zone de recherche comprise entre debut et fin (inclus). Initialement, on a donc debut = 0 et fin égale à la taille du tableau \(- 1\). Cette fonction renvoie -1 si l'élément ne se trouve pas dans le tableau et sinon un indice i tel que tab[i] soit la valeur cherchée.
Proposer un jeu de tests pour votre fonction sous la forme d'instructions assert.
Écrire une version itérative de la recherche dichotomique.

Exercice 8 : Pair et impair¶

On définit les fonctions pair et impair de façon mutuellement récursive de la façon suivante :

l'appel pair(0) renvoie true et l'appel pair(n) renvoie impair(n-1) pour n > 0
l'appel impair(0) renvoie false et l'appel impair(n) renvoie pair(n-1) pour n > 0
Donner une implémentation en C de ces deux fonctions.
Donner une implémentation en OCaml de ces deux fonctions.

Exercice 9 : Chiffres romains¶

En numération romaine, les nombres s'écrivent avec les symboles suivants :

I valant 1
V valant 5
X valant 10
L valant 50
C valant 100
D valant 500
M valant 1000

On lit un nombre de la gauche vers la droite, si la valeur d'un symbole est inférieure à celle du suivant alors on retranche sa valeur du total, sinon on l'ajoute. Par exemple, XIV vaut 14 car la valeur du I doit être retranchée (car inférieure à celle de V).

Écrire une fonction de signature int valeur_symbole(char s) qui renvoie la valeur du symbole donné en argument.

Note

On peut utiliser une suite de if imbriqués ou alors un switch (mais qui n'est pas au programme de MP2I).
Écrire une fonction récursive de signature int valeur(char s[]) qui renvoie la valeur du nombre romain s donné sous la forme d'une suite de caractères.

Exercice 10 : Mélange de Fisher-Yates¶

Le mélange de Fisher-Yates est un algorithme permettant de générer une permutation aléatoire d'un tableau à \(n\) éléments. Il consiste à parcourir le tableau de la fin vers le début, en échangeant l'élément aléatoirement avec un de ceux qui le précèdent, c'est-à-dire que pour l'indice \(i\) variant de \(n-1\) à 1 on échange tab[i] avec tab[j] où \(j\) est choisi aléatoirement entre \(0\) et \(i\).

Proposer une version itérative de cet algorithme.
Proposer une version récursive de cet algorithme.

Aide

On pourra passer en argument en plus du tableau l'indice \(i\).

Exercice 11 : Dessin récursif¶

Attention

L'exercice suivant utilise le module turtle déjà rencontré dans cet exercice du chapitre pointeurs et type structuré.

Dessiner une suite de carrés imbriqués telle que représentée ci-dessous (l'image est de dimension 400x400, le carré initial mesure 300 pixels de côté et la taille diminue ensuite de 30 pixels à chaque carré) :
Si vous aviez donné une version itérative de ce dessin, en faire une version récursive et inversement.

Exercice 12 : Comparaison de deux chaînes de caractères¶

Écrire de façon itérative une fonction compare(chaine1, chaine2) qui renvoie le nombre de fois où chaine1 et chaine2 ont le même caractère au même emplacement. À titre d'exemples :
- compare("recursif", "iteratif") renvoie 2,
- compare("Python", "Javascript") renvoie 0.
Écrire cette même fonction de façon récursive.

Exercice 13 : Retour sur l'exponentiation rapide¶

Rappeler l'algorithme d'exponentiation rapide vu en cours.
En proposer une implémentation (récursive) dans le langage de votre choix.
On s'intéresse maintenant à une implémentation itérative de cet algorithme :
1. Soit \(n \in \mathbb{N}\), on note \(\overline{a_p\dots a_1a_0}^{2}\) son écriture en base 2. Pour tout réel \(x\), donner l'expression de \(x^n\) en fonction des \((a_k)_{0 \leq k \leq p}\).
2. Déduire de l'écriture précédente une implémentation itérative de l'exponentiation rapide.

Exercice 14 : Dessin du flocon de von Koch¶

Attention

L'exercice suivant utilise le module turtle déjà rencontré dans cet exercice du chapitre pointeurs et type structuré.

La courbe de Koch est une figure qui se construit de manière récursive. Le cas de base d'ordre 0 et de longueur \(l\) s'obtient en traçant un segment de longueur \(l\). Le cas récursif d'ordre \(n>0\) s'obtient en traçant successivement quatre courbes d'ordre \(n-1\) et de longueur \(l/3\) de la façon suivante :

vonkoch

À l'aide du module turtle, produire une image telle que ci-dessous qui représente la courbe de Koch d'ordre 5. Le résultat produit ci-dessus a été obtenu grâce à l'appel koch(600, 5) (la largeur de l'image est de 500px et sa hauteur 300).
En utilisant cette fonction, construire le flocon de Koch, c'est-à-dire la figure obtenue en construisant les courbes de Koch sur les trois côtés d'un triangle équilatéral.

Exercice 15 : Tours de Hanoï¶

Inventé par le mathématicien français Édouard Lucas, les tours de Hanoï sont un jeu de réflexion dans lequel on doit déplacer des disques de tailles croissantes (du haut vers le bas) d'une tour de départ à une tour d'arrivée en respectant les contraintes suivantes :

on ne peut déplacer qu'un disque à la fois, celui situé en haut de la tour ;
on ne peut jamais déplacer un disque sur un disque plus petit.

Le but de l'exercice est de résoudre par récursivité le problème des déplacements des \(n\) disques de la tour de départ à la tour d'arrivée.

Faire quelques parties en ligne à cette adresse pour comprendre le jeu.

Résolution automatique par récursivité

Compléter la description de chacune des étapes de la résolution du problème pour 6 disques illustrées ci-dessous :

Etape	Illustration	Descriptions
		6 disques empilés sur la tour 1
		Déplacement de ... disques de la tour 1 vers la tour ....
		Déplacement du disque de la tour ... vers la tour ...
		Déplacement de ... disques de la tour 1 vers la tour ....

Exprimer les étapes et sous la forme de la résolution d'un problème de tours de Hanoï dont on précisera la tour d'arrivée, la tour de départ ainsi que le nombre de disques.
Compléter :

Pour résoudre hanoi à 6 disques :
Résoudre hanoi à ... disques
Déplacer le disque de taille 6
Résoudre hanoi à ... disques
En déduire un algorithme récursif pour résoudre le problème des tours de Hanoï.
Coder et faire fonctionner cet algorithme, on affichera les déplacements sous la forme de printf dans le terminal en précisant les tours d'arrivée et de départ.

Exercice 16 : Tri fusion¶

L'algorithme du tri fusion consiste à :

partager le tableau à trier en deux moitiés (à une unité près),
trier chacune des deux moitiés,
les fusionner pour obtenir la liste triée.

On a schématisé le tri du tableau {10,6,3,9,7,5} suivant ce principe ci-dessous :

    graph TD
    subgraph Partager en deux
    S["{10,6,3,9,7,5}"] --> S1["{10,6,3}"]
    S --> S2["{9,7,5}"]
    end
    subgraph Fusionner
    S1 -.Trier.-> T1["{3,6,10}"]
    S2 -.Trier.-> T2["{5,7,9}"]
    T1 --> T["{3,5,6,7,9,10}"]
    T2 --> T
    end

Le tri des deux moitiés est lui-même effectué par tri fusion, cet algorithme est donc récursif. Le but de l'exercice est d'implémenter cet algorithme en C en générant explicitement à chaque étape les deux moitiés de tableau.

Écrire une fonction affiche qui prend en argument un tableau d'entiers et sa taille, ne renvoie rien et affiche les éléments de ce tableau dans le terminal.
Écrire une fonction fusion qui prend en argument deux tableaux supposés triés (et leur taille) et renvoie le tableau trié issu de leur fusion. Par exemple si tab1 = {3, 6, 10} et tab2 = {5, 7, 9} alors fusion(tab1, 3, tab2, 3) renvoie le tableau {3, 5, 6, 7, 9, 10}.
Aide

On privilégie une solution itérative en utilisant trois indices :
- i1 parcourt le premier tableau,
- i2 parcourt le second tableau,
- i parcourt la fusion des deux.
À chaque étape, soit i1 est incrémenté (quand on prend un élément du tableau 1), soit c'est i2 (quand on prend un élément du tableau 2).
Écrire une fonction partage qui prend en argument un tableau d'entiers tab, deux entiers size1 et size2, et deux tableaux d'entiers moitie1, moitie2 et qui modifie moitie1 et moitie2 afin que moitie1 contienne les éléments de tab d'indice 0..size1-1 et moitie2 ceux d'indice size1...size1+size2-1. Par exemple si tab contient {10, 6, 3, 9, 7, 5} alors après l'appel partage(tab, moitie1, 3, moitie2, 3), moitie1 contiendra {10, 6, 3} et moitie2 contiendra {9, 7, 5}.
Programmer l'algorithme du tri fusion.

Attention

Penser à vérifier l'absence de fuites de mémoire.

Exercice 17 : Suite look and say¶

La suite look and say a pour premiers termes : 1, 11, 21, 1211, 111221, 312211, ... en effet chaque terme s'obtient en regardant puis en disant le terme précédent. Le premier terme 1 se lit "un un" et donc le second terme est 11 qui se lit deux un et donc le troisième terme est 21 qui se lit un deux un un et donc le quatrième terme est 1211 et ainsi de suite. Le but de l'exercice est de générer les termes de cette suite de façon impérative en C puis de façon récursive en OCaml.

Écrire une fonction int chiffre(char c) qui prend en entrée un caractère c appartenant à '0', '1', '2', ..., '9' et renvoie le chiffre correspondant. Par exemple chiffre('7') renvoie l'entier 7.
Écrire en C une fonction char* suivant(char *terme) qui prend en argument une chaîne de caractères terme représentant un terme de la suite et renvoie le terme suivant. Afin d'allouer l'espace mémoire pour le terme suivant, on pourra utiliser un majorant de sa longueur en fonction de celle de terme.
Aide

On pourra procéder en parcourant la chaîne terme tout en mettant à jour deux variables :
- l'une contenant le caractère courant ;
- l'autre son nombre d'apparitions.
Lorsque le caractère suivant n'est pas le caractère courant, on remet à 1 le nombre d'apparitions. On fera bien attention qu'à la fin du parcours, il restera à ajouter le terme en cours de construction.
Tester votre fonction en calculant le 15e terme de la suite :
Faire une conjecture sur les chiffres pouvant apparaître dans les termes de cette suite. Puis prouver cette conjecture (on pourra raisonner par récurrence).
On souhaite maintenant utiliser le fait que les seuls chiffres apparaissant dans la suite look and say sont 1, 2 et 3 afin d'écrire une version récursive du calcul du terme suivant. Pour cela, le cas récursif consiste à considérer les trois premiers chiffres du terme précédent et le cas de base est celui d'un terme contenant moins de 3 chiffres. Écrire cette version récursive en OCaml sous la forme d'une fonction suivant : string -> string qui prend un terme sous la forme d'une chaîne de caractères et renvoie ce terme (toujours sous la forme d'une chaîne de caractères).
En utilisant un programme en OCaml, retrouver la valeur du 15e terme de la suite.

Exercice 18 : Remplissage par diffusion (Flood Fill) et images Netpbm¶

Le remplissage par diffusion (flood fill, ou algorithme du « pot de peinture » dans les logiciels de dessin) permet de colorier une zone connexe délimitée par une frontière dans une image matricielle (grille 2D de pixels).

Partant d'un pixel de départ \((l, c)\) (ligne \(l\), colonne \(c\)), l'algorithme remplace sa couleur par une nouvelle couleur, puis se propage récursivement à ses 4 voisins (haut, bas, gauche, droite) tant qu'ils possèdent la couleur d'origine.

Pour tester cet algorithme, nous allons manipuler des images au format PGM (Portable Graymap). Dans sa variante texte (identifiée par le nombre magique P2), une image en niveaux de gris est stockée dans un simple fichier texte de la forme suivante :

P2
# Largeur Hauteur
12 12
# Valeur maximale du niveau de gris
255
# Niveaux de gris des pixels (séparés par des espaces ou des sauts de ligne)
  0   0   0   0   0   0   0   0   0   0   0   0
  0   0 255 255 255 255 255 255 255 255   0   0
  0 255   0   0   0   0   0   0   0   0 255   0
  0 255   0   0   0   0   0   0   0   0 255   0
  0 255   0   0 255 255 255 255   0   0 255   0
  0 255   0   0 255   0   0 255   0   0 255   0
  0 255   0   0 255   0   0 255   0   0 255   0
  0 255   0   0 255 255 255 255   0   0 255   0
  0 255   0   0   0   0   0   0   0   0 255   0
  0 255   0   0   0   0   0   0   0   0 255   0
  0   0 255 255 255 255 255 255 255 255   0   0
  0   0   0   0   0   0   0   0   0   0   0   0

Vous pouvez télécharger ce fichier de test ici : motif.pgm .

Note

Sous Linux, les fichiers .pgm peuvent être visualisés avec des logiciels comme eog, feh, gimp ou directement ouverts avec un éditeur de texte.

On modélise une image à l'aide de la structure suivante en langage C :
```
typedef struct {
    int largeur;
    int hauteur;
    int maxval;
    int **pixels;
} Image;
```
Écrire une fonction Image* allouer_image(int largeur, int hauteur, int maxval) qui alloue dynamiquement une variable de type Image ainsi que la grille bidimensionnelle de pixels associée (malloc).
Écrire également une fonction void liberer_image(Image *img) qui libère proprement l'ensemble de la mémoire allouée (free).
Lecture d'un fichier PGM :
Écrire une fonction Image* lire_pgm(const char *nom_fichier) qui :
- ouvre le fichier dont le nom est passé en paramètre en mode lecture ("r") à l'aide de fopen et vérifie si l'ouverture a réussi (le pointeur renvoyé n'est pas NULL) ;
- lit l'en-tête (le format P2, la largeur, la hauteur et la valeur maximale maxval) avec fscanf ;
- alloue l'image en mémoire à l'aide de allouer_image ;
- lit ensuite les valeurs de l'ensemble des pixels avec fscanf ;
- ferme le flux à l'aide de fclose et renvoie l'image allouée.
Écriture dans un fichier PGM :
Écrire une fonction void ecrire_pgm(const char *nom_fichier, const Image *img) qui :
- ouvre le fichier en mode écriture ("w") à l'aide de fopen et vérifie le succès de l'ouverture ;
- écrit l'en-tête P2, les dimensions de l'image et la valeur maximale avec fprintf ;
- écrit les pixels ligne par ligne (séparés par un espace, avec un retour à la ligne à la fin de chaque ligne de l'image) ;
- ferme le fichier avec fclose.
Algorithme récursif de remplissage :
Écrire une fonction récursive de signature void flood_fill(Image *img, int l, int c, int ancienne_c, int nouvelle_c) qui :
- s'arrête immédiatement (cas de base) si les coordonnées \((l, c)\) sont en dehors de la grille (\(l < 0\), \(l \ge \text{hauteur}\), \(c < 0\) ou \(c \ge \text{largeur}\)), ou si le pixel en \((l, c)\) ne possède pas la couleur ancienne_c, ou encore si ancienne_c == nouvelle_c ;
- remplace la couleur du pixel \((l, c)\) par nouvelle_c ;
- effectue les 4 appels récursifs sur les pixels voisins : \((l-1, c)\), \((l+1, c)\), \((l, c-1)\) et \((l, c+1)\).
Écrire une fonction void pot_de_peinture(Image *img, int l, int c, int nouvelle_c) qui détermine la couleur d'origine présente aux coordonnées \((l, c)\) puis lance la fonction récursive flood_fill.
Application et test :
Écrire un programme principal (main) qui :
- charge le fichier motif.pgm ;
- applique le pot de peinture au point de coordonnées \((5, 5)\) avec une intensité de gris de valeur \(128\) (pour colorier l'intérieur du petit carré central) ;
- sauvegarde l'image modifiée dans un nouveau fichier motif_rempli.pgm ;
- libère la mémoire de l'image.
  Ouvrir ensuite motif_rempli.pgm pour observer le remplissage obtenu.

Humour d'informaticien¶

Le moteur de recherche Google est connu pour abriter de nombreux easter eggs. Si vous tapez comme recherche le mot recursion, on vous enverra vers la recherche de recursion ...

punition