Note : codes disponibles uniquement en C.
Voyons maintenant comment implémenter en récursif, un programme itératif contenant deux boucles imbriquées :
void afficheRectangle(int nbLignes, int nbColonnes, char caractere) { int ligne, colonne; for (ligne = 0; ligne < nbLignes; ligne++) { for (colonne = 0; colonne < nbColonnes; colonne++) printf("%c", caractere); printf("\n"); } }
On commence par utiliser le principe de transformation d'une simple boucle, en l'appliquant sur la boucle principale. On obtient alors :
void afficheRectangle(int nbLignes, int nbColonnes, char caractere) { int colonne; if (nbLignes == 0) return; for (colonne = 0; colonne < nbColonnes; colonne++) printf("%c", caractere); printf("\n"); afficheRectangle(nbLignes - 1, nbColonnes, caractere); }
On peut alors faire comme si ce programme était un simple programme itératif, et appliquer le principe sur la boucle qu'il contient. Pour que le programme ne fasse aucune boucle, il faut que le nombre de colonnes soit égal à 0. Sinon, on affiche un caractère, puis on rappelle la fonction. Il faut cependant que le rappel de la fonction n'exécute que le contenu de cette boucle, en n'affichant qu'une ligne. On a donc le programme suivant :
void afficheRectangle(int nbLignes, int nbColonnes, char caractere) { if (nbLignes == 0) return; if (nbColonnes == 0) printf("\n"); else { printf("%c", caractere); afficheRectangle(1, nbColonnes - 1, caractere); afficheRectangle(nbLignes - 1, nbColonnes, caractere); } }
On pourrait exprimer en français qu'afficher un rectangle de N lignes M caractères, c'est afficher le premier caractère de la première ligne, puis afficher une ligne de M - 1 caractères, puis afficher N - 1 lignes de M caractères.
Bien sûr, les programmes itératifs sont rarement aussi simples, et en faire des versions récursives peut devenir plus difficile. On a cependant très rarement besoin de le faire, car avec un peu d'habitude, on peut penser directement à la version récursive du problème. Une fois que l'on a l'habitude de manipuler les versions itératives et récursives, on peut choisir plus facilement celle qui est la mieux adaptée à chaque problème.