cours21
Pour bien comprendre la récursivité, il faut d'abord bien comprendre la récursivité.
Nous savons déjà qu'une fonction peut appeler une autre fonction. Par exemple nous faisons cela chaque fois que nous appelons une fonction dans la fonction draw(). Mais une fonction peut-elle s'appeler elle-même ? (oui, draw() peut appeler draw() mais c'est une extrêmement mauvaise idée, vous saurez pourquoi à la fin de ce cours).
Les fonctions qui s'appellent elle-mêmes sont nommées fonctions récursives et sont très pratiques pour résoudre différents types de problèmes. Les plus connus sont souvent les calculs mathématiques qui incluent une récurrence comme la factorielle par exemple. Cette dernière est définie comme :
n! = n × (n - 1) ... 3 × 2 × 1
0! = 1
Nous pourrions bien sûr écrire une fonction qui utilise une boucle for pour résoudre ce problème :
int factorielle(int n) {
int f = 1;
for (int i = 1; i <= n; i++) {
f *= i;
}
return f;
}Cependant, si vous regardez la définition mathématique de la factorielle, vous noterez un fait intéressant, par exemple pour 3! et 4! :
4! = 4 × 3 × 2 × 1
3! = 3 × 2 × 1
donc :
4! = 4 × 3!
Donc de manière plus générale, on peut décrire la factorielle ainsi :
n! = n × (n - 1)!
0! = 1
En d'autres termes, la factorielle de n est n fois la factorielle de n - 1.
Et oui ! La définition de la factorielle inclut la factorielle. C'est presque comme dire que être fatigué est défini par le sentiment que vous éprouvez quand vous êtes fatigués. Ce concept d'auto-référence dans une fonction est appelé récursivité, et nous pouvons l'utiliser pour écrire différemment la fonction factorielle(), de manière à ce qu'elle s'appelle elle-même :
int factorielle(int n) {
if (n <= 1) {
return 1;
} else {
return n * factorielle(n - 1);
}
}Cela peut sembler fou, mais ça fonctionne ! La figure suivante montre ce qui se produit :
Notez le if qui permet de spécifier une condition d'arrêt, c'est à dire le moment où la récursivité s'arrête ! Sans cela on aboutit à une boucle infinie et soit un plantage de Processing car il n'a plus de mémoire, soit une très longue attente !
Si vous vous demandez comment nous avons dessiné la figure ci-dessus, voici la réponse :
Exemple 21.1. Calcul et dessin de factorielle
int textH = 16;
void setup() {
size(700, 300);
background(255);
textFont(createFont("Courier", textH));
factorielle(4, 10, 10 + 3 * textH);
save("fact_execution.png");
}
int factorielle(int n, float x, float y) {
stroke(0);
fill(0);
textAlign(LEFT, TOP);
String s = "factorielle(" + n + ")";
float w = textWidth(s);
text(s, x, y);
float x1 = x + w / 2;
float y1 = y + 3 * textH;
line(x1, y + textH, x1, y1);
triangle(x1, y1, x1 - textH / 4, y1 - textH / 2, x1 + textH / 4, y1 - textH / 2);
String s1 = "return " + n;
if (n > 1) {
s1 += " * ";
}
float w1 = textWidth(s1);
text(s1, x1, y1);
int res = 1;
if (n > 1) {
res = n * factorielle(n - 1, x1 + w1, y1);
}
stroke(255, 0, 0);
fill(255, 0, 0);
textAlign(CENTER, TOP);
float y2 = y - 2 * textH;
line(x1, y, x1, y2);
triangle(x1, y2, x1 - textH / 4, y2 + textH / 2, x1 + textH / 4, y2 + textH / 2);
String s2 = "" + res;
float w2 = textWidth(s2);
text(s2, x1, y2 - textH);
line(x1 - w2 / 2, y2 - textH / 2, x, y2 - textH / 2);
triangle(x, y2 - textH / 2, x + textH / 2, y2 - 3 * textH / 4, x + textH / 2, y2 - textH / 4);
return res;
}Exercice 21.1. Rappelons la définition de la suite de Fibonacci :
F0 = 0
F1 = 1
Fn = Fn-1 + Fn-2
Complétez la fonction suivante qui calcule le n-ième membre de cette suite.
int fibonacci(int n) {
if (___) {
return ___;
} else {
return ___;
}
}Le même principe peut bien sûr s'appliquer aux graphismes avec des résultats intéressants. Regardez par exemple la fonction récursive suivante :
void dessinerCercle(float x, float y, float taille) {
ellipse(x, y, taille, taille);
if(taille > 2) {
taille *= 0.75;
dessinerCercle(x, y, taille);
}
}Que fait dessineCercle() ? Elle dessine une ellipse en fonction de ses paramètres, puis ajuste ces paramètres pour s'appeler à nouveau. Le résultat est une série de cercles !
Bien entendu, une fois de plus nous avons pris soin de s'arrêter si le diamètre du cercle est inférieur à 2. C'est notre condition d'arrêt. Vous l'avez compris, il s'agit d'un commandement :
Une condition d'arrêt tu écriras pour tes fonctions récursives !
C'est même la première chose à laquelle vous devez penser. En effet la récursivité est très similaire à une boucle, et il faut dire quand les boucles s'arrêtent. Si une fonction s'appelle pour toujours, vous serez, au mieux, gratifiés d'un magnifique programme figé.
Le programme précédent est plutôt trivial, puisqu'on pourrait finalement le réaliser avec une boucle. Cependant, des scénarios plus complexes deviennent possibles avec la récursivité, si par exemple, nous appelons récursivement la fonction plus d'une fois. Certains motifs très difficiles à obtenir autrement apparaissent avec un code très élégant. Reprenons notre exemple précédent, mais pour chaque cercle dessiné, nous ferrons deux autres cercles de taille 1/2 à droite et à gauche :
Exemple 21.2. Cercles récursifs
void setup() {
size(400, 400);
background(255);
stroke(0);
noFill();
dessinerCercle(width / 2, height / 2, width / 2);
}
void dessinerCercle(float x, float y, float taille) {
ellipse(x, y, taille, taille);
if (taille > 2) {
dessinerCercle(x + taille / 2, y, taille / 2);
dessinerCercle(x - taille / 2, y, taille / 2);
}
}
Exercice 21.2. Reprenez l'exemple précédent et ajoutez deux lignes de code pour dessiner des cercles au dessus et en dessous. Vous devez obtenir quelque chose qui ressemble à ceci :
Exercice 21.3. Complétez le code ci-dessous. Ce dernier génère le motif suivant :
void setup() {
size(800, 400);
background(255);
stroke(0);
branche(width / 2, height, height / 2);
}
void branche(float x, float y, float h) {
___;
___;
if (___) {
___;
___;
}
}Exercice 21.4. On désire réaliser une règle "récursive" divisant l'écran en deux, puis chacune de ces parties en deux, etc. comme l'indique la figure suivante :
Exercice 21.5. Nous avons déjà généré un « labyrinthe » dans l'exemple 19.4. Le problème avec la génération de murs complètement aléatoire est qu'on ne peut pas être sûr que toutes les cellules seront accessibles. Dans cet exercice nous allons utiliser la récursivité pour assurer l'accessibilité de toutes les cellules. Voici notre algorithme récursif en pseudo-code :
-
On commence par une grande chambre vide.
-
On trace un mur horizontal entre deux lignes de cellules et un mur vertical entre deux colonnes de cellules. Les positions des murs sont aléatoires.
-
On ouvre deux portes horizontales et deux portes verticales à des positions aléatoires pour s'assurer qu'on peut circuler entre les 4 chambres ainsi obtenues.
-
On fait la même chose pour chacune des 4 chambres.
-
On s'arrête lorsque la largeur ou la hauteur d'une chambre devient égale à la taille d'une cellule.
Complétez le code suivant :
void setup() {
size(600, 600);
background(255);
int tailleCellule = 20;
dessinerLabyrinthe(0, 0, width / tailleCellule, height / tailleCellule, tailleCellule);
}
// x1, y1, x2, y2 - coordonnées des deux extrémités de la chambre
// Attention, il s'agit de coordonées "cellule".
// C'est pourquoi on multiplie partout par la taille de la cellule c
void dessinerLabyrinthe(int x1, int y1, int x2, int y2, int c) {
if (x2 - x1 > 1 && y2 - y1 > 1) {
// Choisir aléatoirement les emplacements des murs et des portes
int xMur = int(random(x1 + 1, x2));
int xPorte1 = int(random(x1, xMur));
int xPorte2 = int(random(xMur, x2));
int yMur = int(random(y1 + 1, y2));
int yPorte1 = int(random(y1, yMur));
int yPorte2 = int(random(yMur, y2));
// Mur horizontal avec 2 portes
line(x1 * c, yMur * c, xPorte1 * c, yMur * c);
line((xPorte1 + 1) * c, yMur * c, xPorte2 * c, yMur * c);
line((xPorte2 + 1) * c, yMur * c, x2 * c, yMur * c);
// Mur vertical avec 2 portes
line(xMur * c, y1 * c, xMur * c, yPorte1 * c);
line(xMur * c, (yPorte1 + 1) * c, xMur * c, yPorte2 * c);
line(xMur * c, (yPorte2 + 1) * c, xMur * c, y2 * c);
// On fait la même chose avec les 4 chambres ainsi obtenues
// TODO
}
}
Source xkcd
On doit au mathématicien Wacław Sierpiński un motif fractal qui vers l'infini tend à devenir une surface ... complètement vide !
Au niveau 0 la carpette ressemble à un simple carré remplissant l'écran :
Au niveau 1, on remplace ce carré par huit autres ménageant un vide au centre :
Au niveau 2 on recommence, et donc on remplace chacun de ces carrés par huit autres :
Bien entendu on peut continuer longtemps :
Exercice 21.6. À partir du squelette de code suivant, réalisez une carpette de Sierpiński. Ici au lieu de dessiner à chaque appel récursif, le dessin ne se réalise qu'à la fin.
void setup() {
size(400, 400);
noSmooth(); // Permet au carrés de se juxtaposer...
}
void draw() {
background(255);
fill(40, 80, 200);
stroke(0, 40, 160);
// On commence au niveau 4, la condition d'arrêt stoppe la récursivité
// au niveau 0.
tapisSierpinski(0, 0, width, height, 4);
}
void tapisSierpinski(float x, float y, float w, float h, int niveau) {
if(niveau > 0) {
// TODO
} else {
rect(x, y, w, h);
}
}On doit au mathématicien Édouard Lucas un problème dénommé “les tours de Hanoï” dont l'objectif est de déplacer une tour source constituée de disques de diamètres différents vers une autre tour destination à l'aide d'une tour intermédiaire.
Source Wikipédia
Cependant lors du déplacement il faut respecter deux règles :
- On ne peut déplacer plus d'un disque à la fois,
- On ne peut déplacer un disque que sur autre disque plus grand ou sur un emplacement vide.
Au démarrage les disques sont ordonnés par ordre de grandeur sur la première tour. Voici un exemple de résolution pour une tour de 4 étages :
Source Wikipédia
Nous allons essayer de coder un programme nous permettant de donner les étapes de résolutions pour des tours de tailles arbitraire. Pour ce faire, nous vous proposons bien sûr d'essayer une approche récursive !
Nous allons donc utiliser une fonction récursive ayant la tête suivante :
void hanoi(int n, int source, int destination, int intermediaire) {
}Le paramètre n indique le nombre de disques (commencez par un petit nombre, 3 par exemple).
Les tours sont identifiées par des entiers : 0 pour la source, 1 pour la tour intermédiaire et 2 pour la destination. Nous définirons des constantes SOURCE, INTER et DEST pour les représenter.
Nous allons considérer cette fonction hanoi comme bougeant non pas des disques, mais des tours complètes. Ainsi normalement résoudre le problème revient à appeler (pour 3 disques) :
hanoi(3, SOURCE, DEST, INTER);En s'appelant elle même récursivement, elle se demandera de bouger des sous-tours.
Pour vous aider, vous trouverez plus loin le code d'une classe permettant de stocker l'état des tours et de les dessiner. Cette classe possède deux méthodes :
-
dessiner()Affiche l'état courant des tours. -
deplacer(int source, int destination)déplace un disque d'une toursourceà la tourdestination.
C'est cette classe qui bouge les disques de manière indépendante, et donc c'est la méthode deplacer() qu'il faudra aussi appeler dans hanoi().
Vous aurez certainement besoin d'un papier et d'un crayon ! Une fois que vous aurez réfléchi à un algorithme, vous pourrez passer à l'implantation sur machine. Voici un indice de démarrage : à la première exécution, hanoi() doit :
- déplacer la sous-tour de tous les disques de la tour de départ sauf le plus grand (le dernier), vers la tour intermédiaire.
- ensuite déplacer le plus grand disque restant sur la tour destination,
- enfin replacer la sous tour intermédiaire sur la tour destination.
Voici ci-dessous le code de la classe Tour qui permet de représenter l'état des tours et de déplacer des disques. Attention la fonction deplacer() est impitoyable, et elle arrêtera votre programme si vous essayez de placer un disque sur un disque plus petit, si vous essayez de déplacer un disque inexistant, etc. Il y a des mots-clefs que vous ne connaissez pas encore dans ce code, nous en parlerons après.
final int SOURCE = 0;
final int INTER = 1;
final int DEST = 2;
/** Modélisation des 3 tours et de leur état. */
class Tours {
// Note, on aurait pu modéliser cela en deux classes, une classe Tour, et une classe Tours.
// Ici on choisit de réviser les tableaux à deux dimensions !
/** Nombre de disques. */
int n;
/** Pour chaque tour, taille des disques. */
int[][] tour;
/** Indice de la case la plus haute dans chaque tour. -1 si la tour est vide. */
int[] hauteur;
Tours(int n) {
this.n = n;
tour = new int[3][n];
for (int i = 0; i < n; i++) {
tour[SOURCE][i] = n - i;
}
hauteur = new int[3];
hauteur[SOURCE] = n - 1;
hauteur[INTER] = -1;
hauteur[DEST] = -1;
}
void deplacer(int source, int destination) {
synchronized(this) {
if (hauteur[source] < 0)
throw new RuntimeException("tour source vide");
if (hauteur[destination] == n - 1)
throw new RuntimeException("tour destination pleine");
if (source == destination)
throw new RuntimeException("totologie");
if (hauteur[destination] >= 0 && tour[source][hauteur[source]] > tour[destination][hauteur[destination]])
throw new RuntimeException("attention à la règle 2");
hauteur[destination] += 1;
tour[destination][hauteur[destination]] = tour[source][hauteur[source]];
hauteur[source] -= 1;
}
delay(500);
}
synchronized void dessiner() {
dessinerTour(SOURCE);
dessinerTour(INTER);
dessinerTour(DEST);
}
void dessinerTour(int t) {
float h = height / n;
float w = width / 4;
// Le baton
rectMode(CENTER);
noStroke();
fill(40, 80, 200);
rect(w * (t + 1), height / 2, 20, height);
// Les disques
stroke(100, 40, 0);
fill(200, 80, 40);
for (int i = 0; i <= hauteur[t]; i++) {
rect(w + (w * t), height - (i * h + h / 2), map(tour[t][i], 1, n, 40, w), h);
}
}
}Vous placerez ce code dans un onglet "Tours". Dans l'onglet principal, nous allons devoir faire fonctionner le code d'une manière un peu particulière, voici le code de base, il vous faudra uniquement compléter la méthode hanoi() :
Tours tours;
void setup() {
size(800, 400);
tours = new Tours(4);
}
void draw() {
background(255);
tours.dessiner();
}
void mouseClicked() {
thread("hanoiEnParallele");
}
void hanoi(int n, int source, int destination, int intermediaire) {
if(n > 0) {
___;
___;
___;
}
}
void hanoiEnParallele() {
hanoi(tours.n, SOURCE, DEST, INTER);
}Pour lancer l'exécution il ne reste qu'à cliquer !
Pourquoi autant de difficulté ? N'oubliez pas que Processing réalise le dessin sur l'écran dans une boucle cachée qui appelle la fonction draw() régulièrement. Le soucis est que les choses ne s'affichent à l'écran qu'à la fin de draw(). Or notre fonction hanoi() ne va pas s'arrêter pour laisser draw() s'exécuter et donc elle ne va dessiner que l'état final de l'algorithme (c'est à dire tous les disques empilés sur la dernière tour, dans l'ordre).
Or, ce que nous souhaiterions, c'est que Processing dessine chaque étape de l'algorithme.
Pour réussir ce tour de passe-passe, il nous faut sortir les grands moyens : nous allons créer un processus parallèle d'exécution ! On appelle ces processus des threads (ou fils d'exécution) et leur manipulation est particulièrement délicate.
Nous allons laisser la boucle de dessin de Processing s'exécuter à part et nous allons faire fonctionner notre algorithme récursif de résolution dans un autre processus indépendant. C'est comme du multi-tâche au sein d'un seul programme.
L'intérêt des threads, c'est qu'ils ont accès aux variables des autres threads, et c'est d'ailleurs aussi leur plus grand danger. Car lorsque deux threads accèdent en même temps à la même variable, pour y écrire tous les deux par exemple, le résultat peut être totalement incohérent ! C'est aussi pour cela qu'on nomme ces variables la section critique.
Il faut donc prendre des précautions pour éviter qu'un thread accède à une variable en même temps qu'un autre. Le mot clef synchronized (synchronisé) que vous voyez dans la classe Tours sert à cela. Il permet de s'assurer que les méthodes dessiner() et deplacer() ne sont pas exécutées en même temps. Si l'une est exécutée par un thread, l'autre thread doit attendre.
La commande delay() que vous voyez dans deplacer() sert à demander au processus de résolution d'attendre un peu, de façon à ce que l'on ait le temps de voir ce processus se dérouler. Les valeurs sont en millisecondes, vous pouvez les ajuster.
Enfin, cela explique aussi pourquoi nous utilisons le mot-clef thread() pour lancer un processus indépendant dans mouseClicked. Nous aboutissons à deux threads : le premier est créé automatiquement au démarrage du programme et contient la boucle de dessin draw(), l'autre est créé par nous avec cette commande.
Pour finir en beauté, nous allons vous montrer comment on peut se passer des tableaux en utilisant la récursivité. En cours 15 et 16 nous avons avons joué avec des « serpents ». Nous avons utilisé des tableaux pour stocker les positions des segments de leur corps. Ici nous allons procéder autrement.
Exemple 21.3. Snake récursif
Balle balle;
void setup() {
size(800, 800);
balle = new Balle(10);
}
void draw() {
background(255);
balle.bouger(mouseX, mouseY);
balle.dessiner();
}class Balle {
float x, y;
color c;
Balle suivante;
Balle(int n) {
x = random(width);
y = random(height);
c = color(random(255), random(255), random(255));
if (n > 1) {
suivante = new Balle(n - 1);
}
}
void dessiner() {
if (suivante != null) {
line(x, y, suivante.x, suivante.y);
suivante.dessiner();
}
fill(c);
ellipse(x, y, 20, 20);
}
void bouger(float tx, float ty) {
x = tx;
y = ty;
if (suivante != null) {
suivante.bougerVers(x, y);
}
}
void bougerVers(float tx, float ty) {
x += (tx - x) * 0.01;
y += (ty - y) * 0.01;
if (suivante != null) {
suivante.bougerVers(x, y);
}
}
}Nous créons ce qu'on appelle une liste chaînée de balles. Chaque balle contient une référence vers la balle suivante. Pour la dernière balle cette référence sera null. Rappelons que cette valeur spéciale signifie rien et c'est la valeur par défaut attribuée à des variables de type référence (objets ou tableaux) qui n'étaient pas initialisées avec new. Cette valeur servira de condition d'arrêt de nos appels récursifs.
On utilise une récursivité un peu différente de ce qu'on a vu jusqu'à maintenant. On a vu des fonctions qui s'appellent elles-mêmes, ici nous avons des méthodes qui appellent la même méthode mais sur un autre objet.
Le constructeur prend en argument le nombre de balles dans la liste. D'abord il initialise la position et la couleur de la balle. Ensuite, si ce n'est pas la dernière balle (n > 1), il crée la balle suivante, qui de son côté va créer encore n - 1 balles.
Quand on dessine une balle, on commence par dessiner les balles suivantes, s'il y en a (suivante != null). Et quand on bouge une balle, les balles suivantes se déplacent vers elle.
Le programme principal manipule uniquement la première balle dans la liste. C'est celle-ci qui va se charger de la deuxième balle (sa suivante) qui à son tour ... bref, vous connaissez l'histoire.
La tortue graphique est une façon de dessiner popularisée par le langage de programmation Logo. Nous avons une « tortue » que nous pouvons contrôler avec des instructions de type « tourne à d degrés » et « avance p pixels ». En se déplaçant, elle laisse une trace qui est notre dessin. Il est très facile de implanter une tortue en Processing :
class Tortue {
float x, y;
float direction;
Tortue(float x, float y) {
this.x = x;
this.y = y;
direction = 0;
}
void tourner(float angle) {
direction += angle;
}
void avancer(float longueur) {
float xDestination = x + longueur * cos(direction);
float yDestination = y + longueur * sin(direction);
line(x, y, xDestination, yDestination);
x = xDestination;
y = yDestination;
}
}Et voici comment on peut l'utiliser pour dessiner par exemple un triangle équilatéral :
Tortue tortue;
void setup() {
size(400, 400);
background(255);
tortue = new Tortue(50, 100);
tortue.avancer(300);
tortue.tourner(2 * PI / 3);
tortue.avancer(300);
tortue.tourner(2 * PI / 3);
tortue.avancer(300);
}En combinant la tortue et la récursivité, on peut obtenir des résultats intéressants.
Exercice 21.7 La courbe de Koch est obtenue de la façon suivante :
- Au niveau 0 c'est un simple segment de droite
- Pour obtenir la courbe de niveau
n, on divise chaque segment de la courbe de niveaun - 1en trois et on remplace le segment du milieu par deux segments de la même longueur :
Complétez la fonction suivante :
void courbeKoch(int niveau, float longueur) {
if (niveau == 0) {
tortue.avancer(longueur);
} else {
// TODO
}
}qui dessine une courbe de Koch. Appelez-la à partir de setup().
Dessinez maintenant le flocon de Koch qui n'est rien d'autre qu'une combinaison de trois courbes de Koch.
Exercice 21.8 À l'aide de la tortue et la récursivité, dessinez d'autres courbes, par exemple celle du dragon.