Voir les cours et résoudre les problèmes en :
Le C est un langage de programmation impératif conçu pour la programmation système. Inventé au début des années 1970 avec UNIX, C est devenu un des langages les plus utilisés. De nombreux langages plus modernes se sont inspirés de sa syntaxe. Il privilégie la performance sur la simplicité de la syntaxe. [En savoir plus]
Le C++ est un langage de programmation impératif. Inventé au début des années 1980, il apporte de nouveaux concepts au langage C (les objets, la généricité), le modernise et lui ajoute de nombreuses bibliothèques. C++ est devenu l'un des langages les plus utilisés. Sa performance et sa richesse en font le langage de prédilection pour les concours. [En savoir plus]
Pascal est un langage de programmation impératif inventé dans les années 1970 dans un but d'enseignement. Quoiqu'encore utilisé à cette fin, l'absence de bibliothèque standard en limite son utilisation malgré une grande efficacité. Sa syntaxe a été reprise par d'autres langages plus modernes avec plus ou moins de succès. [En savoir plus]


Remarque : Les cours pour ce langage ne sont disponibles que jusqu'au chapitre 4, « Lecture de l'entrée ». Les corrections sont toutefois toujours fournies.
OCaml est un langage de programmation fonctionnel inventé au milieu des années 1990. Il permet aussi une programmation impérative ou objet. Il permet d'écrire des programmes courts et faciles à vérifier et est ainsi utilisé pour certains systèmes embarqués très sensibles comme ceux des avions. Il est utilisé dans l'enseignement en classes préparatoires aux grandes écoles. [En savoir plus]


Remarque : Les cours pour ce langage ne sont disponibles que jusqu'au chapitre 4, « Lecture de l'entrée ». Les corrections sont toutefois toujours fournies.
Java est un langage de programmation impératif et orienté objet. Inventé au début des années 1990, il reprend en grande partie la syntaxe du langage C++ tout en la simplifiant, au prix d'une performance un peu moins bonne. S'exécutant dans une machine virtuelle, il assure une grande portabilité et ses très nombreuses bibliothèques en font un langage très utilisé. On lui reproche toutefois la « verbosité » de son code. [En savoir plus]


Remarque : Pour un débutant souhaitant apprendre Java, nous conseillons fortement de commencer par JavaScool, plus facile à apprendre, bien que fortement similaire.
Java's Cool (alias JavaScool) est conçu spécifiquement pour l'apprentissage des bases de la programmation. Il reprend en grande partie la syntaxe de Java sur laquelle il s'appuie, mais la simplifie pour un apprentissage plus aisé. La plateforme JavaScool est accompagnée d'un ensemble d'activités diverses de découverte de la programmation. [En savoir plus]
Python est un langage de programmation impératif inventé à la fin des années 1980. Il permet une programmation orientée objet et admet une syntaxe concise et claire qui en font un langage très bien adapté aux débutants. Étant un langage interprété, il n'est cependant pas aussi performant que d'autres langages. [En savoir plus]

Note : codes disponibles uniquement en C.

Factorielle en itératif et récursif

Les exemples d'utilisation des fonctions récursives que nous avons vus jusqu'à présent avaient tous une nature récursive, car ils mettaient en oeuvre des éléments imbriqués les uns dans les autres. Comme nous allons le voir, il aurait tout à fait été possible de programmer ces exemples sans utiliser de fonctions récursives. De la même manière, il n'est pas nécessaire qu'un problème ait en lui-même une nature récursive, pour qu'il soit possible de le résoudre très simplement avec une fonction récursive.

Prenons par exemple le calcul de la factorielle d'un nombre, une fonction mathématique qui pour une valeur entière positive, retourne le produit de tous les entiers entre 1 et cette valeur. Pour une valeur nulle, la fonction retourne 1. Par exemple, la factorielle de 5, que l'on note "5!", vaut 1*2*3*4*5 = 120.

On peut écrire la fonction factorielle sous la forme d'une simple boucle, de la manière suivante :

int factorielle(int valeur)
{
   int total = 1;
   int curValeur;
   for (curValeur = 1; curValeur <= valeur; curValeur++)
      total *= curValeur;
   return total;
}

Il est cependant possible de donner une définition récursive de la fonction factorielle :

La factorielle d'un nombre N vaut 1 si N est égal à 0, et N multiplié par la factorielle de N - 1 sinon.

Cette définition est parfaitement équivalente à la précédente, et peut se traduire en code par une fonction récursive :

int factorielle(int valeur)
{
   if (valeur == 0)
      return 1;
   else
      return valeur * factorielle(valeur - 1);
}

On peut remarquer que le code de cette deuxième version est plus simple que la version avec une boucle, et qu'il peut se lire quasiment comme une définition.

La première version, qui utilise une boucle, est ce que l'on appelle une implémentation itérative de la fonction factorielle : on effectue un certain nombre d'itérations d'une boucle. La deuxième version s'appelle tout simplement l'implémentation récursive.

Avantages et inconvénients

Une grande partie des problèmes peut se résoudre avec une implémentation récursive, comme avec une implémentation itérative. L'une ou l'autre peut paraître plus ou moins naturelle suivant le problème, ou suivant les habitudes du programmeur. Avec un peu d'habitude, utiliser l'implémentation récursive permet souvent d'avoir un programme plus simple, plus facile à comprendre, donc à débugger.

L'implémentation récursive a cependant deux principaux inconvénients, qui peuvent être gênants dans certains cas :

  • Un appel de fonction prend plus de temps qu'une simple itération de boucle.
  • Un appel de fonction utilise une petite quantité de mémoire.

Le premier inconvénient fait que des programmes implémentés avec une fonction récursive seront souvent légèrement plus lents que leurs équivalents itératifs. Si le moindre gain de vitesse pour cette partie de votre programme est important, il peut donc être préférable d'utiliser une implémentation itérative. Dans le cas contraire, la perte de performances peut être largement compensée par le gain en clarté du code, donc en réduction de risques de laisser des bugs.

Le deuxième inconvénient peut être très gênant si le nombre d'appels imbriqués est très important. Chaque appel de fonction imbriqué utilise une certaine quantité de mémoire, plus ou moins importante selon le nombre de paramètres et de variables de votre fonction. Cette mémoire est libérée dès que l'exécution de la fonction se termine, mais dans le cas d'une fonction récursive, cette quantité de mémoire est multipliée par le nombre d'appels imbriqués à un moment donné. Si ce nombre d'appels imbriqués peut atteindre des centaines de milliers, voire des millions, on peut facilement atteindre des méga-octets de mémoire, pour un calcul qui ne prendrait aucune mémoire avec une fonction itérative.

Dans le cas du calcul de la factorielle, le nombre d'appels récursifs imbriqués est égal à la valeur passée en paramètre. En pratique, on ne peut pas dépasser 12, car 13! vaut plus de 4 milliards, donc que le résultat du calcul ne peut être stocké dans un entier 32 bits. La mémoire utilisée est alors négligeable.

Dans certains cas, le compilateur est capable d'éviter de lui-même ces deux inconvénients, en transformant automatiquement votre fonction récursive en un programme itératif. Ceci reste cependant assez rare, et il ne faut donc pas trop compter dessus avec les compilateurs actuels.

Itératif vers récursif : simple boucle

Un programme itératif se base sur des boucles pour traiter un certain nombre d'éléments. Un programme itératif simple peut donc ressembler à l'exemple suivant, qui affiche un certain nombre de fois un caractère :

void afficheLigne(int nbAffichages, char caractere)
{
   int affichages;
   for (affichages = 0; affichages < nbAffichages; affichages++)
      printf("%c", caractere);
   printf("\n");
}

Pour écrire une version récursive de ce programme, on commence par se demander dans quel cas la boucle n'est pas du tout utilisée. En l'occurence, il s'agit du cas où le paramètre nbAffichages vaut 0, donc qu'on ne fait qu'afficher le retour à la ligne. On peut alors commencer à écrire une fonction qui gère ce cas :

void afficheLigne(int nbAffichages, char caractere)
{
   if (nbAffichages == 0)
      printf("\n");
}

Reste à gérer le cas où il y a des choses à afficher. Le principe de la fonction récursive est qu'elle s'occupe d'une seule étape, et laisse les étapes suivantes pour les appels imbriqués. Dans le cas où il y a des caractères à afficher, la fonction doit donc afficher un caractère, puis se rappeler, avec comme paramètre le nombre de caractères restant à afficher. Il s'agit de la valeur qu'on lui a transmise, diminuée de 1 :

void afficheLigne(int nbAffichages, char caractere)
{
   if (nbAffichages == 0)
      printf("\n");
   else
   {
      printf("%c", caractere);
      afficheLigne(nbAffichages-1, caractere);
   }
}

Cette fonction réalise exactement la même chose que la version itérative. On peut ainsi dire en français : pour afficher une ligne de N caractères, il faut afficher un caractère, puis afficher une ligne de N-1 caractères.

Pensez à vous inscrire pour valider les cours et résoudre les exercices.