14. récursion

Une méthode récursive est une méthode qui fait appel à elle-même (directement ou indirectement). En général, l'appel à soi-même se fait sur un objet différent, ou sur le même objet, mais avec des paramètres différents. (si on utilise toujours le même objet avec la même méthode et les mêmes paramètres, on risque d'avoir une récursion infinie - par analogie avec une boucle infinie).
[revoir la formulation]

Exemple : le dessin de la figure ci-dessus utilise typiquement une méthode récursive.

On remarque que c'est toujours le même schéma qui est reproduit, de plus en plus petit.

class Tortue extends SuperTortue{

    void arbre(int longueur, int x, int y){
        Coordonnee c;
        double dir;
        saute(x,y);
        tourneGauche(40);
        avance(longueur);
        c = position();
        dir = directionRadians();
        if ((longueur/2)>5){
           arbre(longueur/2, c.x(), c.y());
        }
        for (int i=0; i<2; i++){
            directionRadians(dir);
            saute(x,y);
            tourneDroite(60);
            avance(longueur);
            c = position();
            dir = directionRadians();
            if ((longueur/2)>5){
               arbre(longueur/2, c.x(), c.y());
            }
        }
    }
}

public class MonProg14a{

public static void main(String[] args){

Tortue rosalie = new Tortue();

rosalie.arbre(150, 250, 450);
}
}
MonProg14a.java

Attention de ne pas faire une récursion sans fin ! Ici, si on n'a pas la condition if ((longueur/2)>5) le programme ne dessinerait que

Exercices

Créez une méthode récursive qui permette de dessiner le schéma suivant :

un carré, dont chacun des coins est le centre d'un autre carré. La longueur du côté des petits carrés correspond à la moitié de la longueur du grand carré.

Pour chacun des petits carrés, on réapplique le même schéma et ainsi de suite.

Pour éviter une récusion infinie, il faut fixer une longueur minimale pour le côté des carrés. Pour l'image ci-dessus, le carré de base a un côté de 200pt et la méthode ne dessine que des carrés dont le côté est plus grand que 10pt.

Autre indication : votre méthode aura la signature suivante :
void carreRec(int longueur, int x, int y)
longueur : longueur du côté, x et y sont les coordonnées du centre du carré

Solution (MonProg14b.java)
Autre solution (MonProg14c.java) plus lisible ;-)

Créez une méthode récursive qui permette de dessiner un flocon comme :

le schéma de base est puis

Solution (MonProg14d.java)

8/1/2001
CLMJ