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]
Boucles en récursif

Reprenons la fonction affiche_entiers qui prend en paramètre un entier debut et un entier fin et qui affiche tous les entiers compris entre ces deux valeurs incluses. On en a deux versions.

La première avec une boucle for :

let affiche_entiers debut fin =
  for i = debut to fin do
     print_int !i;
     print_string " ";
  done;
  in

Et la seconde avec une boucle while :

let affiche_entiers debut fin =
  let i = ref debut in
  while !i <= fin do
     print_int !i;
     print_string " ";
     incr i;
  done;
  in

On va en voir une troisième version sans aucune boucle, juste avec du récursif. Vocabulaire : les codes utilisant des boucles for ou while sont des codes dits "itératifs".

On va transformer cette fonction en une fonction récursive, à partir du principe qui suit. Pour afficher tous les nombres entre debut et fin, si debut <= fin, on commence par afficher la valeur de debut, et ensuite on affiche tous les nombres entre debut+1 et fin. Lorsque debut > fin, il n'y a rien à faire.

let rec affiche_entre debut fin =
  if debut <= fin then
     begin
     print_int debut;
     print_string " ";
     affiche_entre (succ debut) fin;
     end;
  in

Pour utiliser une fonction récursive, c'est exactement pareil que pour les autres. Un exemple :

affiche_entiers 23 54;

On n'a pas gagné beaucoup de lignes avec la version récursive, mais il n'y a plus de références. Par conséquent, le code est donc plus facile à comprendre (du moins une fois qu'on s'est habitué au principe du récursif).

Débordement de pile

Pour déterminer la parité d'un entier n, on a vu que l'on pouvait utiliser l'expression ((n mod 2) = 0) qui est true si et seulement si n est pair. On va ici écrire une fonction qui fait la même chose sans utiliser l'opérateur mod, en utilisant une fonction récursive.

Le principe est le suivant : si n = 0, on retourne vrai, et si n est strictement positif, on retourne l'opposé de la parité de n-1. Voici le code, que l'on teste sur l'entier 3.

let rec est_pair n =
  if n = 0
     then true
     else not (est_pair (pred n))
  in

print_string (string_of_bool (est_pair 3));

Pour trouver la parité de 3, on calcule récursivement celle de 2, puis celle de 1, et enfin celle de 0. Mathématiquement, comme 0 est pair, son suivant 1 est impair, et donc 2 est pair, et par conséquence 3 est impair. Du point de vue des robots, est_pair 0 est true, donc est_pair 1 est not true, c'est-à-dire false, et ainsi de suite...

Essayez maintenant la fonction sur l'entier 100 millions :

let rec est_pair n =
  if n = 0
     then true
     else not (est_pair (pred n))
  in

print_string (string_of_bool (est_pair 100000000));

Vous obtiendrez le message d'erreur suivant :

Fatal error: exception Stack_overflow

Le code est tout à fait correct, et devrait théoriquement afficher true, mais là le programme plante. Cela est dû à la limitation de la mémoire : au bout d'un moment il n'y aura plus de place pour créer un nouveau robot, et le programme génère une erreur. Plus précisément, la mémoire utilisée par un programme pour stocker les robots qu'il utilise s'appelle la pile. Lorsque la pile est pleine et qu'on veut rajouter encore un robot, elle déborde.

Un trop grand nombre d'appels récursifs imbriqués provoque un débordement de pile (stack overflow).

Il est utile de savoir jusqu'où on peut aller. Par tâtonnements successifs, on s'aperçoit que est_pair 65470 est la dernière valeur que l'on peut calculer. Attention, cette valeur 65470 dépend à la fois de la fonction récursive sur laquelle on travaille, mais aussi de la machine sur laquelle le programme est exécuté.

La limitation de la pile est une contrainte qu'il ne faut pas oublier, car après tout, une centaine de milliers est un petit nombre pour un ordinateur. Heureusement, il y a différentes solutions pour contourner ce problème comme on le verra plus tard.

Récursion infinie
Pouvez-vous deviner ce qu'il va se passer si l'on fait :
let rec factorielle n =
  if n = 1
     then 1
     else n * (factorielle (n-1))
  in

print_int (factorielle (-3));

Testez aussi ce code pour voir ce qu'il se passe. Vous devriez obtenir encore un débordement de pile :

Fatal error: exception Stack_overflow

Suivons ce qui se passe. Un premier robot prend en paramètre l'entier -3. Comme n est différent de 1, un robot assistant va être appelé. Cet assistant va prendre en paramètre l'entier n - 1, c'est-à-dire -4, et va faire appel à un troisième robot. Ce dernier prendra le paramètre -5, et appeler un quatrième robot, etc...

Comme n ne fait que décroître, il ne sera jamais égal à 1, et on va avoir besoin sans cesse de nouveau robots. Et fatalement, on fait tôt ou tard déborder la pile. La récursivité infinie est l'analogue de la boucle while infinie : la condition qui est censé faire qu'on s'arrête au bout d'un moment n'est jamais vérifiée.

Un stack overflow a souvent pour cause la récursivité infinie.

Remarque : sans la contrainte de la mémoire, le programme s'arrêterait au bout d'un moment, et ce à cause de la limitation des entiers. Souvenez-vous que l'entier juste en dessous -1073741824 est 1073741823. Lorsqu'on part d'un négatif, et qu'on descend suffisamment longtemps, on finit par arriver sur 1.

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