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).

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.

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.