Fractales

  Considérons d'autres exemples de programmes récursifs. Des exemples spectaculaires sont le cas de fonctions graphiques fractales. Nous utilisons les fonctions graphiques du Macintosh (cf. page ). Un premier exemple simple est le flocon de von Koch [11] qui est défini comme suit

 
Figure: Flocons de von Koch 

Le flocon d'ordre 0 est un triangle équilatéral.
Le flocon d'ordre 1 est ce même triangle dont les côtés sont découpés en trois et sur lequel s'appuie un autre triangle équilatéral au milieu.
Le flocon d'ordre consiste à prendre le flocon d'ordre en appliquant la même opération sur chacun de ses côtés.

Le résultat ressemble effectivement à un flocon de neige idéalisé. L'écriture du programme est laissé en exercice. On y arrive très simplement en utilisant les fonctions trigonométriques sin et cos. Un autre exemple classique est la courbe du Dragon. La définition de cette courbe est la suivante: la courbe du Dragon d'ordre 1 est un vecteur entre deux points quelconques et , la courbe du Dragon d'ordre est la courbe du Dragon d'ordre entre et suivie de la même courbe d'ordre entre et (à l'envers), où est le triangle isocèle rectangle en , et est à droite du vecteur . Donc, si et sont les points de coordonnées et , les coordonnées de sont    

 
Figure: La courbe du Dragon

La courbe se programme simplement par

procedure Dragon (n: integer; x, y, z, t: integer);
    var u, v: integer;
    begin
    if n = 1 then
        begin
        MoveTo (x, y);
        LineTo (z, t);
        end
    else
        begin
        u := (x + z + t - y) div 2;
        v := (y + t - z + x) div 2;
        Dragon (n-1, x, y, u, v);
        Dragon (n-1, z, t, u, v);
        end;
    end;

Si on calcule Dragon , on voit apparaître un petit dragon. Cette courbe est ce que l'on obtient en pliant 10 fois une feuille de papier, puis en la dépliant. Une autre remarque est que ce tracé lève le crayon, et que l'on préfère souvent ne pas lever le crayon pour la tracer. Pour ce faire, nous définissons une autre procédure DragonBis qui dessine la courbe à l'envers. La procédure Dragon sera définie récursivement en fonction de Dragon et DragonBis. De même, DragonBis est définie récursivement en termes de DragonBis et Dragon. On dit alors qu'il y a une récursivité croisée . En Pascal, on utilise le mot clé forward pour cela.

procedure DragonBis (n: integer; x, y, z, t: integer);
    forward;
 
procedure Dragon (n: integer; x, y, z, t: integer);
    var u, v: integer;
    begin
    if n = 1 then
        begin
        MoveTo (x, y);
        LineTo (z, t);
        end
    else
        begin
        u = (x + z + t - y) div 2;
        v = (y + t - z + x) div 2;
        Dragon (n-1, x, y, u, v);
        DragonBis (n-1, u, v, z, t);
        end;
    end;

procedure DragonBis;
    var u, v: integer;
    begin
    if n = 1 then
        begin
        MoveTo (x, y);
        LineTo (z, t);
        end
    else
        begin
        u = (x + z - t + y) div 2;
        v = (y + t + z - x) div 2;
        Dragon (n-1, x, y, u, v);
        DragonBis (n-1, u, v, z, t);
        end;
    end;

Remarque de syntaxe: Pascal (comme C) exige que les types des procédures soient définis avant toute référence à cette procédure, d'où la déclaration forward. Mais Pascal (à la différence de C) exige aussi que la vraie définition de la procédure se fasse sans redéclarer la signature de la fonction (pour éviter de vérifier la concordance de types entre la signature des deux déclarations de la même fonction ou procédure!)

Il y a bien d'autres courbes fractales comme la courbe de Hilbert, courbe de Peano qui recouvre un carré, les fonctions de Mandelbrot. Ces courbes servent en imagerie pour faire des parcours ``aléatoires'' de surfaces, et donnent des fonds esthétiques à certaines images.