Discussion :

[Chatanga]

Ma tentative de le faire sans récursion, parce que c'est plus marrant :

Code C++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
const int DX[] = { 1, 0, -1, 0 };
const int DY[] = { 0, 1, 0, -1 }; // DY = DX[(i + 3) % 4]
 
void step(int x, int y) {
   printf("x=%d, y=%d\n", x, y);
}
 
void walk(int xMax, int yMax) {
   // A chaque itération, on ressert le contour à parcourir.
   for (int x1 = 0, y1 = 0, x2 = xMax, y2 = yMax; x1 < x2 && y1 < y2; ++x1, ++y1, --x2, --y2) {
       // On commence en haut à gauche et on réalise un contour complet en 4 étapes.
       int x = x1;
       int y = y1;
       for (int i = 0; i < 4; ++i) {
           // Le vecteur précalculé de déplacement à l'étape i.
           int dx = DX[i];
           int dy = DY[i];
           do {
               // Dans le cas d'un contour plat (x2-x1=1 et/ou y2-y1=1),
               // on ne marque pas les cases en dehors.
               if (x1 <= x && x < x2 && y1 <= y && y < y2) {
                   step(x, y);
               }
               x += dx;
               y += dy;
           } while (x1 <= x + dx && x + dx < x2 && y1 <= y + dy && y + dy < y2);
       }
   }
}
 
int main(int, char **) {
    walk(5, 2);
    return EXIT_SUCCESS;
}

Ca marche aussi avec des tailles du type 0x6, 1x1, 3x1, etc. Mine de rien, ce sont des cas aux limites bien pénibles (du moins en non récursif).

[Invité]

Bonjour,
Moi, je préfère cette méthode plutôt que la récursivité. Je n'utilise la récursivité que rarement, par exemple pour les arbres.
Je pense surtout à la pile et au contre-exemple du calcul de !n.
Pour le cas précis j'aurais peut-être été un peu plus détaillé, c'est à dire faire 4 boucles successives au lieu d'une seule avec 4 compteurs.

[Goten]

Les arbres ça se parcour aussi sans récursivité ... tant qu'a faire.
Mais bon, de nos jours je vois pas l'intérêt d'éviter la récursivité, tant que c'est bien placé et bien réfléchi. (la majorité des compilo implémentent le TCO)

[Invité]

Bonjour Goten,

de nos jours ...

C'est vrai mais il y a tellement longtemps que j'ai commencé à développer, que certaines méthodes sont restées des habitudes. En Fortan on était obligé de trouver des astuces pour "tromper le compilateur" si on voulait faire des fonctions récursives.
Je suis resté avec cette façon de penser qui consiste à dire que si on est dans environnement où on doit faire exactement la même chose que ce qui a amené à entrer dans cet environnement, alors c'est de la récursivité, sinon c'est de la répétition, bouclage.
Dans le cas présent de remplissage avec décalage, pour moi, c'est plutôt du bouclage que de la récursivité.
En cas de récursivité, il serait impossible de commencer par la fin, en cas de bouclage, cela ne présenterait, généralement, aucune difficulté.