On commence par étudier le premier appel qui a lieu dans le main() : p(4).

Avec la valeur 4, cela donne pour la suite :

p(2); printf("%3d",4); p(3);

Déjà il est prévisible que le nombre 4 sera donné en sortie à un moment donné. Faisons de même pour les appels p(2) et p(3) et les suivants… la représentation va prendre l'allure d'un arbre :

Les appels ont lieu si n>0, il n'y a donc pas d'appel pour n=-1 et n=0. À chaque fois qu'il n'y a plus d'appel récursif, la suite des instructions de l'appel courant est effectuée, c'est-à-dire l'affichage de la valeur de n. L'arbre va se lire de gauche à droite : il revient pour afficher n après chaque appel à gauche de p(0) ou p(-1) ce qui donne :

2 1 4 1 3 2 1

Avec cette méthode on voit que des sous-arbres se répètent, ce sont les appels p(1).

Cette fois nous allons partir à l'inverse, par le bas avec le dernier appel possible lorsque n=1 et nous allons remonter ensuite pour la valeur immédiatement supérieure ce qui donne :

p(1) : 1
p(2) : p(0) 2 p(1) soit 2 1
p(3) : p(1) 3 p(2) soit 1 3 2 1
p(4) : p(2) 4 p(3) soit 2 1 4 1 3 2 1

Soit un entier de valeur 45671, il s'agit d'afficher successivement les caractères 4, 5, 6, 7, 1 et non plus la valeur de l'entier. Pour ce faire, tant que le résultat est supérieur à 0 on prend le modulo 10 qui donne le dernier chiffre, on divise par 10 et on recommence. En itératif cela donne :

void chiffreIter (int val)
{
    while (val>0){
        printf("%d_", val%10);
        val/=10;
    }
}

La version récursive est très simple, il suffit de remplacer la boucle par un appel récursif :

void chiffre(int val)
{
    if (val>0){
        printf("%d_", val%10);
        chiffre(val/10);
    }
}

Un produit factoriel c'est : n! = 1*2*3*…*n. La définition est :

n! = 1 si n=0
n! = n(n-1)! si n>0

Il s'agit d'une fonction de récurrence et on boucle sur n tant que n>0, voici une version de fonction itérative :

int factIter (int n)
{
int res=1;
    while (n>1)
        res*=n--; // attention décrémentation après multiplication
    return res;
}

D'une certaine façon, la version récursive peut sembler plus facile, plus proche de la définition du calcul. Si n est égal à 0, la fonction retourne 1, sinon la fonction retourne n*(n-1), ce qui donne :

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

Éventuellement l'écriture peut être rendue plus concise avec l'opérateur conditionnel :

int fact(int n)
{
    return n>1 ? n*fact(n-1) : 1;
}

Il s'agit d'une suite établie comme suit :

Pour n >= 0

Par exemple pour les valeurs de 0 à 8 nous avons :

Voici une version itérative de la fonction :

int fibIter(int n)
{
int i,res,f1,f2;
    if (n<=1)
        res=n;
    else{
        f2=0;
        f1=1;
        for (i=2; i<=n; i++){
            res=f2+f1;
            f2=f1;
            f1=res;
        }
    }
    return res;
}

La version récursive est finalement plus naturelle :

int fib(int n)
{
    if (n<=1)
        return n;
    else
        return fib(n-2)+fib(n-1);
}

L'opérateur conditionnel peut rendre encore plus concise l'écriture :

int fib(int n)
{
    return n<=1 ? n : fib(n-2)+fib(n-1);
}

De base 10 vers base B pour un nombre positif et avec 0 < B <=16

À chaque étape on prend le modulo du nombre en base 10 selon la base B donnée puis on divise le nombre en base 10 par la base B. Pour la version itérative, le résultat obtenu commence par la plus petite unité : il est donné à l'envers. Par exemple pour 160 en base 10 passé en base 8, on obtient successivement 0, 4, 2 et il faut lire le résultat en commençant par la fin : 240. La solution consiste à empiler le résultat obtenu à chaque étape du calcul et lorsque le calcul est terminé de dépiler pour afficher dans le bon ordre chaque chiffre obtenu, ce qui donne :

void conversionIter (int val, int base)
{
int pile[100];
int sommet=0;
    while (val>0){
        pile[sommet++] = val % base;
        val /= base;
    }
    for (--sommet; sommet>=0; sommet--)
        if(pile[sommet]<=9)
            printf("%d",pile[sommet]);
        else
            printf("%c",pile[sommet]-10+'A');
}

La version récursive évite la gestion de la pile du fait de l'empilement des appels successifs :

void conversion (int val, int base)
{
static char chif[]="0123456789ABCDEF"; // de 0 à 15
    if (val/base != 0)
        conversion(val/base,base);
    printf("%c",chif[val%base]); // vaut entre 0 et 15 compris
}

De base B vers base 10 pour un nombre positif et sans lettre pour l'hexadécimal

Le principe est d'utiliser la notation étendue qui permet de décomposer un nombre.

Par exemple 123 en base 8 donne en base 10 l'addition :

1*82 + 2*81 + 3*80 = 83

La version itérative calcule chaque étape en commençant par la droite et les ajoute une par une. Ainsi 3*80 s'obtient en faisant (123%10)*1 (un nombre à la puissance 0 vaut toujours 1).

Ensuite :

2*81 s'obtient avec ((123/10)%10)*8
1*82 s'obtient avec ((12/10)%10)*8*8

À chaque tour le nombre obtenu est additionné au résultat précédent.

Le principe est toujours le même, quels que soient au départ le nombre et sa base.

Pour l'algorithme, il est important de dissocier la division par 10 du reste obtenu avec modulo 10. Au départ le résultat est un modulo 10. Ensuite, à chaque tour la valeur donnée est divisée par 10 tant qu'elle est supérieure à 0. À chaque tour également est pris le modulo 10 de la nouvelle valeur obtenue. La base est multipliée par elle-même et le résultat stocké au fur et à mesure dans une variable b. Le produit de chaque tour est ajouté au résultat final, ce qui donne :

int convert10Iter (int val, int base)
{
int res,b,r;
    b=1;
    res=val%10;
    while (val>0){
        val=val/10;
        r=val%10;
        b*=base;
        res+=r*b;
    }
    return res;
}

La version récursive est un peu plus concise :

int convert10(int val, int base)
{
    if (val/10 ==0)
        return val%10;
    else
        return convert10(val/10,base)* base + val % 10;
}

Pour calculer xⁿ, on multiplie n fois x par lui-même, par exemple 3⁴=3*3*3*3. La fonction récursive correspondante donne :

int puissance(int x, int n)
{
    if (n==0)
        return 1;
    else
        return x*puissance(x,n-1);
}

ou en utilisant l'opérateur conditionnel :

int puissance(int x, int n)
{
    return (n==0) ? 1 :x*puissance(x,n-1);
}

Le temps de calcul peut être diminué en ne calculant que la moitié puis en multipliant cette moitié par elle-même, par exemple pour 3⁴ faire simplement 3² puis 3² * 3². Dans le cas d'un exposant impair, il suffit de multiplier une fois de plus par la base x, par exemple :

3⁵ = 3² * 3² * 3

Ainsi pour xⁿ le calcul se ramène à trouver x^{n / 2}, le multiplier par lui-même et si n est

impair, multiplier une fois par x en plus. Ce principe peut être implémenté de façon

récursive de la manière suivante :

int puissance2(int x, int n)
{
int res;
    if (n==0)
        res = 1;
    else{
        res=puissance2(x, n/2);
        if(n%2==0) // si pair
            res=res*res;
        else
            res=res*res*x;
        }
    return res;
}

Soient deux nombres entiers x et y dont un au moins n'est pas nul, pgcd(x,y), c'est le nombre entier le plus grand par lequel x et y sont divisibles. Par exemple :

pgcd(1000,600)     = 200
pgcd(-70,90)     = 10
pgcd(0,12)         = 12

L'algorithme repose sur quelques remarques :

1. pgcd (x,y) = pgcd (y,x) ;
2. si d divise x et y, d divise aussi x - y soit la propriété : pgcd (x,y) = pgcd (x-y,x) ;
3. pcgd(x,0) = 0.

Le principe de l'algorithme est de soustraire du plus grand des deux nombres le plus petit. Par exemple :

pgcd(1900,700)     = pgcd(1200,700)    // remarque 2
            = pgcd(500,700)    // remarque 2
            = pgcd(700,500)    // 1
            = pgcd(200,500)    // 2
            = pgcd(500,200)    // 1
            = pgcd(300,200)    // 2
            = pgcd(100,200)    // 1
            = pgcd(200,100)    // 2
            = pgcd(100,100)    // 2
            = pgcd(0,100)    // 2
            = pgcd(100,0)    // 1
            = 100            //

En fait le résultat est obtenu lorsque x et y sont égaux. Ainsi, tant que x et y sont différents, à chaque tour : si x est inférieur à y on permute x et y, et ensuite on soustrait y de x, ce qui donne :

int pgcd(int x, int y)
{
int t;
    while (x != y){
        if (x < y){
            t = x;
            x = y;
            y = t;
        }
    x -= y;
    }
    return x;
}

Attention, cet algorithme ne prend pas en compte des nombres négatifs ni le fait que dès le départ x ou y peuvent être égaux à 0.

Pour diminuer le nombre de tours, il est possible d'utiliser l'opérateur modulo plutôt que de faire une soustraction. En effet, x%y vaut le reste de la division de x par y, par exemple 1900%700 vaut directement 500 sans avoir à faire 1900-700 et 1200-700.

On remarque également que l'expression x%y est nécessairement inférieure à y. Alors plutôt que d'écrire :

puis de permuter, on peut écrire directement :

pgcd(x,y) = pgcd( y, x%y)

et appliquer cette règle tant que y est différent de 0.

Par exemple pgcd(1900,700) ne prend plus que 5 étapes :

pgcd(1900,700)     = pgcd(700,500)
            = pgcd(500,200)
            = pgcd(200,100)
            = pgcd(100,0)
            = 100

Tant que y est supérieur à 0 on calcule m = x % y, ensuite on affecte y à x et on met m dans y, ce qui donne en itératif quatre instructions :

int pgcd(int x, int y)
{
int m;
    while(y){
        m=x%y;
        x=y;
        y=m;
    }
    return x;
}

La version récursive permet de permuter directement les paramètres (y passé en x et x%y passé en y) du coup la fonction qui en découle est simplifiée :

int pgcd(int x, int y)
{
    if (y)
        return pgcd(y,x%y);
    else
        return x;
}

Et une seule ligne avec l'opérateur conditionnel :

int pgcd(int x, int y)
{
    return (y) ? pgcd(y,x%y) : x;
}

Lors d'un appel récursif, la fonction reste la même, mais les valeurs passées aux paramètres

changent. L'objectif est ici de tracer une règle graduée du type :

La graduation est marquée par des marques régulières, pour chaque section il y a une marque aux moitiés de section, une marque plus petite aux quarts de section, une marque encore plus petite aux huitièmes de section, etc. Cet exercice illustre la technique récursive du « diviser pour résoudre » souvent utilisée dans des problématiques d'optimisation et des algorithmes de tris. Les données sont divisées et ne se recouvrent jamais (on ne repasse pas deux fois au même endroit).

La graduation est obtenue en traçant un trait de hauteur h toujours à la moitié m du segment courant et récursivement de tracer un trait de hauteur h-1 à la moitié m/2 du segment précédent. On suppose une fonction trace() pour tracer le trait vertical, cette fonction dépend de l'environnement. Elle prend en paramètres la position horizontale du trait et sa hauteur. Ici nous utilisons très simplement un affichage console du nombre correspondant à la hauteur à la bonne place horizontalement. De plus chaque hauteur a sa propre couleur pour faciliter la lecture du résultat. La fonction nécessite les fonctions gotoxy() et textcolor() données en annexe. Ce qui donne :

void trace(int hpos, int h)
{
    gotoxy(hpos,0);
    textcolor(15-h);
    printf("%d",h);
}

Les graduations de la règle sont obtenues avec la fonction :

void regle(int gauche, int droite, int hauteur)
{
int milieu=(gauche+droite)/2;
    if (hauteur>0){
        trace(milieu,hauteur);
        regle(gauche,milieu,hauteur-1);
        regle(milieu,droite,hauteur-1);
    }
}

Si hauteur n'est pas nulle, la fonction commence par tracer un trait de « hauteur » au milieu du segment [gauche,droite] puis elle s'appelle deux fois pour « hauteur-1 », une fois pour le segment [gauche,milieu] et une fois pour le segment [milieu,droite]. Prenons par exemple un segment de 0 à 8 et une hauteur de 3, au départ nous avons l'appel :

regle( 0, 8, 3) ensuite :
    tracer (4,3)
    regle(0,4,2)
        tracer (2,2)
        regle (0,2,1)
            tracer (1,1)
            regle (0,1,0)
            regle (1,2,0)
        regle (2,4,1)
            tracer (3,1)
            regle (2,3,0)
            regle (3,4,0)
    regle (4,8,2)
        tracer (6,2)
        regle (4,6,1)
            tracer (5,1)
            regle (4,5,0)
            regle (5,6,0)
        regle (6,8,1)
            tracer (7,1)
            regle (6,7,0)
            regle (7,8,0)

Avec la fonction trace() ci-dessus, nous obtenons pour cet appel :

1 2 1 3 1 2 1

Avec les appels :

regle(0,16,4) nous obtenons la suite : 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1

regle(0,32,5) nous obtenons :

1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1

On distingue du point de vue des appels comme du résultat la forme d'un arbre :

Cet arbre sous-jacent correspond à l'arbre d'appels. Voici par exemple l'arbre d'appels pour regle(0,8,3), il reprend le détail de la reconstitution des appels ci-dessus sans indiquer l'ordre chronologique du parcours :

Il s'agit d'un arbre binaire complet : à chaque nœud de l'arbre partent deux branches jusqu'aux extrémités, appelées les feuilles de l'arbre. Le premier nœud est appelé la racine de l'arbre.

Le nombre total de nœuds d'un arbre binaire complet est en rapport avec sa hauteur h : c'est 2^h-1.

En l'occurrence c'est pratique ici pour obtenir la taille de notre règle en fonction de la hauteur qu'on lui donne : pour une hauteur de 3 il faut 2³-1 = 7 graduations, pour une hauteur de 4 il faut 2⁴-1 = 15 graduations, pour une hauteur de 5, 2⁵-1 = 31, etc. Le nombre total de feuilles correspond lui à 2h, le nombre de feuilles par niveau correspond à 2niveau avec 0 pour le niveau racine.

La version itérative de la règle consiste à tracer chaque niveau de l'arbre en commençant par celui du bas et en les superposant au fur et à mesure. Par exemple pour regle(0,15,4) cela donne :

Les valeurs de graduation (1,2,3,4) de chaque nouvelle ligne remplacent celles de la précédente, ce qui donne une seule ligne :

void regleIter(int g, int d, int h)
{
int i,pas,j,m;
for (i=1,pas=1,m=(g+d); i<=h; i++,pas*=2,m/=2)
for (j=0; j<m;j++)
trace((pas+pas*j)-1,i); // -1 pour partir du bord
}

Avec la récursion, il est souvent difficile de départager le très simple du très complexe et une description récursive apparemment élémentaire peut faire apparaître des figures très complexes notamment dans le domaine graphique.

Par exemple nous voulons maintenant, sur le mode de la règle graduée, non plus tracer des traits (que nous avons remplacés par des chiffres ci-dessus) mais tracer des cercles. La fonction a en paramètres une position (x,y) et un rayon r, elle trace le cercle puis s'appelle elle-même récursivement deux fois : une en (x-r/2,y) et une (x+r/2). Le test d'arrêt est r inférieur à une valeur donnée, ce qui donne :

void deuxCercles(int,x, int y, int r)
{
int r2=r/2;
    if (r<5){
        trace_cercle(x,y,r);
        deuxCercle(x-r2,y,r2);
        deuxCercle(x+r2,y,r2);
    }
}

Cette fois, il vaut mieux passer en mode graphique et utiliser un environnement comme Allegro ou SDL qui fournissent des fonctions de dessin. Voici un exemple d'exécution de la fonction recCercles() définie ci-après. Cette fonction utilise les fonctions de la bibliothèque Allegro makecol() pour la couleur et circlefill() pour le tracé de cercle. Dans cet exemple, l'appel de la fonction est paramétré avec la position x,y au centre de l'écran et un rayon de 150 pixels de la façon suivante :

recCercles(SCREEN_W/2,SCREEN_H/2,150);

Voici la fonction complète :

void recCercles(int x, int y, int r)
{
int r2=r/2;
int color;
    if (r>5){
        color=makecol(rand()%256,rand()%128, rand()%64);
        circlefill(screen,x,y,r,color);
        recCercles(x-r2, y, r2);
        recCercles(x+r2, y, r2);
    }
}

La fonction makecol() produit une couleur aléatoire et la fonction circlefill() trace un cercle (se référer à la documentation Allegro ou SDL pour tester).

Même principe, mais cette fois avec des carrés. Au départ on trace un carré à partir d'une position x,y et d'une moitié de côté. La fonction a trois paramètres : la position x,y et le demi-côté c. Elle s'appelle elle-même quatre fois, une pour chaque coin du carré avec un côté divisé par deux à chaque fois. La récursion a lieu jusqu'à ce que le côté soit au-dessous d'une valeur seuil :

void carre(int x,int y,int c)
{
int cc=c/2
    if (c>2){
        // ici dessiner le carré de centre x,y et de demi-côté c
        carre(x-c,y-c,cc);
        carre(x+c,y-c,cc);
        carre(x+c,y+c,cc);
        carre(x-c,y+c,cc);
    }
}

On peut obtenir différentes figures, selon le choix des couleurs et un tracé plein ou juste le tour des carrés. Le premier exemple ci-dessous est obtenu avec des carrés pleins en blanc sur fond noir, le second avec juste le tour des carrés noir sur fond blanc :

La fonction ci-dessous utilise la fonction rect() qui trace le contour d'un rectangle de l'environnement Allegro.

void carre(int x, int y, int c)
{
int cc=c/2;
int color;
    if (c>2){
        color=makecol(rand()%256,rand()%128, rand()%64);
        rect(screen,x-c,y-c,x+c,y+c,color);
        carre(x-c,y-c,cc);
        carre(x+c,y-c,cc);
        carre(x+c,y+c,cc);
        carre(x-c,y+c,cc);
    }
}

L'objectif est d'obtenir un dessin tel que le dessin ci-dessous :

Pour ce faire, on trace un segment et récursivement, à l'issue de chaque segment, on trace n segments nouveaux. Chaque segment est tracé à partir d'une position x,y, d'une longueur et d'un angle donné, ce qui détermine une position rx, ry d'arrivée du segment :

La position d'arrivée du segment, la fin d'une branche de l'arbre, sera la position de départ de plusieurs autres branches. Il est donc important de récupérer cette position d'arrivée du segment pour pouvoir tracer les suivants. Pour une position x,y, les coordonnées du point rx,ry sont obtenues en appliquant les formules mathématiques suivantes :

rx = x + longueur * cosinus de l'angle
ry = y + longueur * sinus de l'angle

Voici la fonction permettant de tracer un segment sans couleur et qui suppose une fonction de tracé de trait fournie par un environnement de développement graphique :

#define PI 3.1416
#define DEGRE 2*PI/360.0
void segment(int l,int x,int y,int angle, int*rx,int*ry)
{
int i;
    // récupération des coordonnées du point d'arrivée
    *rx = x + l*cos(angle*DEGRE);
    *ry = y l*sin(angle*DEGRE);
    // plusieurs traits pour faire l'épaisseur des branches en
    // fonction de la longueur
    for (i=0; i<l/15; i++)
        tracer_ligne(x+i,y,*rx+i,*ry);
}

La position d'arrivée du segment est transmise au contexte d'appel via un passage par référence aux paramètres pointeurs int*rx,*ry.

Voici la même fonction adaptée pour l'environnement Allegro de programmation graphique :

void segment(int l,int x,int y,int angle, int*rx,int*ry)
{
int i,color;
    *rx = x + l*cos(angle*DEGRE);
    *ry = y l*sin(angle*DEGRE);
    color=makecol(rand()%32,rand()%256,rand()%128);
    //color=makecol(0,0,0); // pour avoir du noir
    for (i=0; i<l/15; i++)
        line(screen,x+i,y,*rx+i,*ry,color);
}

Une fois le tracé de segment résolu, reste l'essentiel : tracer l'arbre. En gros cette nouvelle fonction dessine_arbre() trace un segment d'une hauteur donnée à partir d'une position x,y et selon un angle donné. La position d'arrivée du segment tracé est récupérée, la hauteur est diminuée et si la hauteur est toujours supérieure à 1 pixel on appelle récursivement la fonction dessine_arbre() n fois. Si n est fixe, le nombre de branches sera toujours le même, mais on peut introduire une valeur aléatoire pour qu'il n'y ait pas toujours le même nombre de branches. Reste la question de l'angle pour le tracé de chaque nouveau segment à chaque nœud de l'arbre. L'idée est de répartir les directions entre -π/2 et π/2 soit un éventail de 180 degrés divisé selon le nombre des branches à tracer et incliné à chaque fois de 90 degrés. Pour la fonction de base suivante, la hauteur h reste fixe et à chaque passage elle est diminuée d'un tiers. Le nombre des branches est fixe également, à chaque nœud il y a toujours le même nombre de branches, ce qui donne :

void dessine_arbre(int h, int x,int y, int angle)
{
int rx,ry,n,i,ev;
    segment(h,x,y,angle,&rx,&ry);
    h=h*2/3;
    if (h>1){
        n=3;
        ev=180/n;
        for (i=1; i<=n; i++)
            dessine_arbre(h,rx,ry,angle-90-ev/2+i*ev);
    }
}

Dans la version ci-dessous, des déséquilibres sont ajoutés qui introduisent des dissymétries, c'est le paramétrage qui donne la première image de l'arbre ci-dessus :

void dessine_arbre(int h, int x,int y, int angle)
{
int rx,ry,n,i,ev;
    // dissymétrie aléatoire sur la taille des segments
    // (entre 0 et 10% en plus de h)
    h= h+0.1*(rand()%h);
    segment(h,x,y,angle,&rx,&ry);
    h=h*2/3;
    if (h>1){
        // le nombre de branches est compris entre 1 et 7
        n=1+rand()%8;
        ev=180/n;
        for (i=1; i<=n; i++)
            dessine_arbre(h,rx,ry,angle-90-ev/2+i*ev);
    }
}

Le labyrinthe est situé dans un rectangle avec une ouverture sur un bord au départ. Une case du labyrinthe correspond à un trésor à atteindre. Il n'y a pas de circuit bouclé dans le labyrinthe.

L'objectif est de réaliser un programme capable de trouver le butin en cherchant le chemin à travers un labyrinthe. Nous allons travailler en mode console pour le tester.

Le labyrinthe

Le rectangle dans lequel se trouve le labyrinthe est une matrice d'entiers de TX par TY déclarée en global et initialisée avec le dessin d'un labyrinthe dans le programme :

#define TX         26
#define TY         20
static int MAT[TY[TX]={
{0,0,0,0,0,0,0,0,0,0,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,1,1,1,1,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0},
{0,0,1,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,0},
{0,1,1,0,0,1,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0},
{0,1,0,0,0,0,1,1,1,0,1,1,1,1,1,0,1,0,1,1,1,1,0,0,1,0},
{0,1,0,0,0,0,0,1,0,0,0,0,0,0,1,0,1,0,0,0,0,1,0,1,1,0},
{0,1,0,0,1,1,1,1,0,0,0,1,0,0,1,0,1,0,1,1,0,1,0,1,0,0},
{0,1,1,1,1,0,0,0,0,0,0,1,0,0,1,1,1,0,0,1,0,1,0,1,0,0},
{0,0,0,0,0,0,0,1,0,0,0,1,1,1,1,0,0,0,0,1,0,1,0,1,0,0},
{0,0,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,1,1,0},
{0,0,0,0,0,0,0,1,0,0,0,1,1,1,1,1,0,0,0,0,1,0,0,0,1,0},
{0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,1,1,1,1,1,0,0,0,1,0},
{0,1,0,0,1,1,1,1,1,1,1,0,1,0,0,0,0,0,0,0,1,1,1,0,1,0},
{0,1,1,1,1,0,0,0,0,0,0,0,1,0,2,0,0,1,1,1,0,0,1,0,1,0},
{0,0,0,0,1,0,0,1,1,1,1,1,1,0,1,0,0,0,0,1,0,0,1,1,1,0},
{0,0,0,0,1,0,0,1,0,0,0,0,1,1,1,1,0,0,1,1,1,1,1,0,0,0},
{0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,1,1,0,0},
{0,0,1,1,1,1,1,1,0,1,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0},
{0,1,1,0,0,0,0,1,1,1,0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0} };

Dans la matrice, les positions à 0 correspondent aux murs, les positions à 1 à un chemin, la position à 4 est le point de départ et la position à 2 le point d'arrivée. Ces nombres vont permettre de déterminer des couleurs pour l'affichage, mais aussi le trajet à effectuer. Le but à atteindre et les murs sont identifiés par deux macros :

#define BUT 2 // pour la couleur du trésor
#define MUR 0 // pour la couleur mur

La matrice du labyrinthe est toujours utilisée comme variable globale dans la suite du programme et ne fait pas l'objet d'un paramètre de fonction.

Affichage du labyrinthe

Pour afficher ce labyrinthe en mode console, nous utilisons trois fonctions fournies dans l'environnement : gotoxy() pour déplacer le curseur en écriture à une position x,y de la fenêtre, console textcolor() pour obtenir une couleur parmi les 16 possibles et putchar() pour afficher un caractère à la position du curseur dans la fenêtre console. gotoxy() et textcolor() sont données en annexe et putchar() est dans la bibliothèque standard stdio.h.

La première étape est d'afficher un caractère à une position donnée et d'une couleur donnée. Le caractère affiché est toujours un espace, ce caractère prend toujours la couleur du fond (sans lettre par-dessus). En mode console, la couleur est codée sur 4 bits (16 couleurs) mais le codage utilise 8 bits. Sur les 4 premiers bits de l'octet tient la couleur de la lettre et sur les 4 suivants la couleur du fond. Pour avoir une couleur de fond entre 0 et 15, il faut décaler une valeur choisie entre 0 et 15 de 4 octets vers la gauche. Voici la fonction d'affichage d'une position :

void affiche_posi(int x, int y, int color)
{
    gotoxy(x,y);
    textcolor( color<<4);
    putchar(' ');
}

Ensuite il reste à appeler cette fonction pour chaque position de la matrice afin d'obtenir le dessin dans la fenêtre console. Chaque position de la matrice contient sa couleur : 0 pour noir, 1 pour bleu foncé, 2 pour vert foncé, 4 pour rouge foncé. Voici la fonction d'affichage du labyrinthe :

void affiche_laby()
{
int x,y,color;
    for (y=0; y<TY; y++)
        for(x=0; x<TX; x++)
            affiche_posi(x,y,MAT[y][x]);
}

La recherche du chemin

Pour voir le chemin s'afficher progressivement, nous devons ralentir l'exécution. Pour ce faire, voici une petite fonction d'attente selon la durée passée en paramètre (en millisecondes, mais cela dépend des environnements) :

void attendre(int dure)
{
int start=clock();
    while (clock()<start+dure){}
}

Les directions possibles pour la recherche sont 0 vers nord, 1 vers est, 2 vers sud et 3 vers ouest. L'objectif est de trouver la case sur BUT, de colorer la recherche effectuée puis le chemin trouvé, ce qui donne en mode console la fonction récursive suivante :

int chemin (int x,int y,int olddir)
{
int i,nx,ny;
    // 1
    if (MAT[y][x]==BUT)
        return 1;
    // 2
    if (MAT[y][x]!=MUR ){
        // 3
        attendre(40);
        affiche_posi(x,y,BLEUCLAIR);
        // 4
        for (i=0;i<4;i++)
            if(i!= (olddir+2)%4 ){
                // 5
                nx=x+(i%2)*(2-i);
                ny=y+((i+1)%2)*(i-1);
                // 6
                if (chemin(nx,ny,i)){
                    // 7
                    attendre(45);
                    affiche_posi(x,y,ROUGE);
                    return 1;
                }
            }
    }
    return 0;
}

(1) C'est le test d'arrêt de la fonction récursive lorsque le but est atteint : elle retourne 1.

(2) Sinon, il faut que la position x,y soit sur un chemin, si on est sur un mur, pas d'appel récursif non plus et retour de 0.

(3) Si on est sur un chemin, affichage de la position en bleu clair. La fonction attendre() provoque un ralentissement pour rendre l'animation de la recherche visible (sinon c'est quasi instantané).

(4) Ensuite, partir dans toutes les 4 directions pour continuer la recherche. Il faut éviter cependant de retourner en arrière, c'est-à-dire qu'il faut éviter la direction inverse de celle d'où l'on arrive (si on allait vers le sud, il faut éviter juste après d'aller vers le nord). On remarque aussi l'importance de l'ordre donné pour la recherche. Ici on essaie toujours dans le même ordre nord-est-sud-ouest. Le simple fait d'inverser cet ordre et faire ouest-sud-est-nord donne une recherche très différente. L'idéal est d'avoir toujours un ordre différent, c'est-à-dire une combinaison aléatoire des chiffres 0,1,2,3 à chaque tour. Ce point est abordé un peu plus loin avec la création du labyrinthe.

(5) Là il s'agit de prendre les nouvelles coordonnées nx,ny en fonction de la direction i. Possibilité de faire un switch et procéder au cas par cas, mais pour une direction i donnée, la formule (i%2)*(2-i) donne -1, 0 ou 1 à ajouter à x et la formule ((i+1)%2)*(i-1) donne -1, 0 ou 1 pour ajouter à y.

(6) Appel récursif de la fonction chemin() pour la nouvelle position nx,ny en précisant la direction prise (ce qui permet en 4 d'éviter le retour en arrière). La fonction retourne 0 si rien n'est trouvé et 1 si le but est atteint.

(7) Si le but est atteint, la position trouvée passe en rouge et la fonction retourne 1 également, de sorte que le chemin qui a mené à la solution passe progressivement en rouge depuis le but jusqu'au point de départ, au fur et à mesure du dépilement des fonctions concernées.

Le principe pour la création d'un labyrinthe sans circuit bouclé à l'intérieur est de creuser au départ un bloc de mur, c'est-à-dire une matrice de 0 (MUR). On creuse un chemin de façon à ne jamais recouper le chemin déjà creusé. Pour ce faire, on avance dans la galerie en creusant le mur de deux en deux cases dans une des quatre directions possibles choisies au hasard. À chaque fois les cases creusées prennent la valeur 1 définie par la macro CHEMIN. Seules les cases sur MUR sont creusables ce qui fait qu'il y a impossibilité de revenir en arrière ou de recouper le chemin déjà creusé. La fonction est récursive et, à chaque étape, la fonction s'appelle elle-même quatre fois, une pour chaque direction. L'important alors est que ces appels ne soient pas toujours dans le même ordre, de façon à ce que le cheminement du labyrinthe soit imprédictible. Pour ce faire, avant d'aborder la fonction de création du labyrinthe, voici comment sont obtenues des suites de directions toujours différentes.

Suite de directions toujours différentes

Chaque suite de directions (0 pour nord, 1 pour est, 2 pour sud, 3 pour ouest) est stockée dans un tableau de quatre entiers. Au départ, elles sont dans l'ordre de 0 à 3 ensuite, elles sont mélangées un peu comme des cartes, ce qui donne :

void init_dir(int d[4])
{
int i,i1,i2,tmp;
    for (i=0; i<4; i++)
        d[i]=i;
    for (i=0; i<50;i++){
        i1=rand()%4;
        i2=rand()%4;
        if(i1!=i2){
            tmp=d[i1];
            d[i1]=d[i2];
            d[i2]=tmp;
        }
    }
}

Le labyrinthe

La fonction a en paramètre la position x,y courante dans le labyrinthe. Cette position est censée pouvoir faire partie du chemin creusé, on commence par la convertir en CHEMIN. À partir de là, une suite de directions est stockée dans un tableau de quatre entiers avec la fonction init_dir(). Puis, dans une boucle for, un switch() est réalisé sur chacune des positions du tableau. Pour chaque direction, on va regarder à 2 unités plus loin (+ ou -2 selon direction et en x ou en y) si c'est du MUR et en vérifiant préalablement que l'on reste toujours dans la matrice. Lorsque ces deux conditions sont vérifiées, le MUR est remplacé par du CHEMIN sur la case adjacente dans la direction donnée et la fonction est appelée récursivement à partir de la position suivante obtenue (+ ou -2 selon direction en x ou en y), ce qui donne :

void creuse_laby(int x,int y)
{
int d[4];
int i;
    MAT[y][x]=CHEMIN;
    init_dir(d);
    for (i=0; i<4; i++)
        switch(d[i]){
            case 0 :
                if (y>1 && MAT[y-2][x]== MUR){
                    MAT[y-1][x]= CHEMIN;
                    creuse_laby(x,y-2);
                }
                break;
            case 1 :
                if (x<TX-2 && MAT[y][x+2]== MUR){
                    MAT[y][x+1]= CHEMIN;
                    creuse_laby(x+2,y);
                }
                break;
            case 2 :
                if (y<TY-2 && MAT[y+2][x]== MUR){
                    MAT[y+1][x]= CHEMIN;
                    creuse_laby(x,y+2);
                }
                break;
            case 3 :
                if (x>1 && MAT[y][x-2]== MUR){
                    MAT[y][x-1]= CHEMIN;
                    creuse_laby(x-2,y);
                }
                break;
        }
}