Voici enfin la page Récursivité, ça veut dire qu'on avance ;-) ! Mais attention, cette page vous apprendra ce qu'il y a de plus important dans le tutoriel. Je vous assure qu'il y aura des exercices sur ce sujet à TOUS vos contrôles !!!
Si jamais vous avez des doutes sur les variables, les types (classiques) et les fonctions, je vous conseille fortement de retourner en arrière (de quelques pages :-/ !) afin de maîtriser au mieux tout ça.
Pour plus d’informations sur la récursivité: Wikipédia. Vous n'êtes pas obligé de comprendre entièrement cette page, mais il y a beaucoup de choses intéressantes sur le sujet.

La Récursivité Classique

let rec NomDeVotreFonction Paramètre1 Paramètre2 ... =
  instruction
  instruction
  ...
;;

let rec facto x =
 if x = 1 then 1
 else x * facto (x-1);;

let rec facto x =
 if x = 1 then 1
 else x * facto (x-1);
(*Ceci est un commentaire OCaml !*)

print_string "Cette fonction renvoie: ";;
print_int (facto 4);; (*La fonction facto renvoie forcément un int !*)
print_newline();;

Cette fonction renvoie 24 (* Je confirme que 4! = 24 ;-) *)

Attention, print_int ne prend qu'un seul paramètre ! Donc si vous ne mettez pas les parenthèses vous aurez une erreur. Les parenthèses donnent la priorité au calcul de facto de 4.

Le Cas D'Arrêt

Alors c'est simple la condition d'arrêt est la chose la plus importante dans les fonctions récursives!
C'est aussi la première chose que vous devez écrire !!

let rec facto x =
 if x = -1 then 1 (* Cette ligne est le cas d'arrêt *)
 else x * facto (x-1);;

print_int (facto 4);; (* What else ? *)

Je fais exprès de fixer le cas d'arrêt : pour x = -1 renvoyer 1 !

0

Ce résultat était prévisible ! On a :
facto 4 = 4 * 3 * 2 * 1 * 0 * 1 = 0 On a l'air bien *%ù££$$ pour le coups :-P (je suis nul en Maths mais je sais que c'est incorrect) !

Si vous ne mettez pas de cas d'arrêt du tout :

let rec facto x = x * facto (x) in print_int (facto 4);;


Et bien ...

Fatal error: exception Stack_overflow


Ocaml va tout développer, et se rendre compte qu'il va faire ça à l'infini :

facto 4 = 4 * 3 * 2 * 1 * **0** * (-1) * (-2) .... (-10) * (-11) ....
Donc même message d'erreur **overflow**. D'ailleurs, vous remarquez qu'un des facteurs est 0, donc le tout doit être nul, mais il renvoie quand même l'erreur.
Ocaml est vraiment nul, il faut tout lui dire ^_^.

Le cas d'arrêt porte bien son nom, il indique à la fonction quand s’arrêter (un peu comme les bornes des boucles en C !).
Ce cas d'arrêt est primordial à la survie de vos fonctions récursives 8-) !

Le Paramètre Variant

Vous vous souvenez de notre fonction facto ?

let rec facto x =
 if x = 1 then 1
 else x * facto (x-1);

Le paramètre variant est le paramètre que l'on appelle dans la fonction récursive (ici facto). Ici c'est (x-1), donc à chaque récursion le paramètre variant décrémente.
Si dans votre fonction récursive vous appelez mal ou pas du tout ce paramètre variant vous aurez des erreurs.
Erreur à ne pas faire:

let rec facto x =
 if x = 1 then 1
 else x * facto (x);

print_int (facto 4);; (* C'est mon chiffre préféré c'est pour ça. *)

Résultat:

Fatal error: exception Stack_overflow

Là encore c'était prévisible ! Que se passe-t-il dans ce programme ? 4 * 4 * 4 * 4 .... * 4 * 4 * 4 * 4 et ça à l'infini ! Or OCaml a la flemme de faire cette opération à l'infini, on le comprend :-D ! Dès qu'il en a marre, il vous gueule qu'il y a une erreur //overflow//. On en retient, au lieu d'appeler facto avec x on va l'appeler avec (x-1).
** Donc une fonction récursive s'appelle elle-même mais le paramètre avec lequel on l'appelle doit varier ! C'est à vous de voir comment doit évoluer ce paramètre variant, tout dépend de ce que vous voulez faire ;-) (il peut incrémenter, décrémenter ou autre ...) ! **

Récapitulons, pour que notre fonction récursive fasse ce que l'on veut:

- On rappelle la fonction avec un paramètre différent à chaque appel.
C'est à vous de voir comment évolue le paramètre variant.

- On oublie pas le cas d'arrêt.
Là encore tout dépend de ce que vous voulez faire.

Posez vous les questions :

- Comment doivent varier le(s) paramètre(s) ?

- Dans quel(s) cas ma fonction doit s'arrêter ?

Malgré toutes ces conditions, il est encore possible de faire réaliser à la fonction facto une boucle infinie.
Essayez d'appeler facto (-4). En effet, la fonction factorielle n'est pas définie pour les entiers négatifs.

Afin d'éviter que les entiers négatifs soient pris en compte, on peut utiliser 3 fonctions :
- failwith
- invalid_arg
- assert

Le Traitement des Erreurs

Failwith et invalid_arg se ressemblent beaucoup et sont suivies par une chaîne de caractère.
En revanche, assert s'utilise avec un booléen.

Un petit exemple pour la route ?

let div x y= match x with |0 -> failwith "div par 0"
                |_-> y/x;;

let div x y= match x with |0 -> invalid_arg "div par 0"
               |_-> y/x;;

let rec facto x = assert (x > 0); (* assert doit être mis au début de chaque fonction *)
 if x = 1 then 1
 else x * facto (x-1);;

Dans les deux exemples de divisions, au lieu du message d'erreur classique "Division_by_zero", on a les messages que nous avons définis.

Exemple de Récursivité

Comment faire une fonction qui calcule le PGCD (Plus Grand Commun Diviseur) de deux nombres x et y ?
Pour visualiser la fonction, il faut se rappeler l'algorithme à faire quand vous êtes en maths :
Quel est le pgcd 34 12 ?

34 = 12 * 2 + 10
12 = 10 * 1 + 2
10 = 5 * 2 + 0
On s'arrête ici car le reste de 10 / 5 est nul ! Donc le PGCD de 34 et 12 est **2**.

D'après vous, notre fonction sera-t-elle récursive ?
A chaque ligne de mon algorithme, je reproduit la ligne précédente mais avec des valeurs différentes. Donc elle sera certainement récursive.
Le diviseur de la première ligne **2** est le dividende de la deuxième.
Le diviseur de la deuxième ligne **10** est le dividende de la troisième.
On s'arrête à la troisième ligne car 10 / 5 n'a pas de reste.

Notre fonction a besoin d'un cas d'arrêt : on a dit que l'on s'arrêtait dès que ** le reste de la division x par y est nul **. Pour gérer ce cas en OCaml, on utilise : **(x mod y = 0)**.
Notre fonction (1^ère version) :

let rec pgcd x y =
 if (x mod y = 0) then y;;

Malheureusement cette fonction n'est pas récursive. Il y a bien un rec mais pgcd ne s'appelle pas elle-même ! De plus, cette fonction ne gère pas les cas quand on a (x mod y <> 0). Et pourtant, c'est nécessaire.

Notre fonction (2^ème version avec cas d'arrêt) :

let rec pgcd x y =
 if (x mod y = 0) then y
 else pgcd y (x mod y);;
(* Dans la dernière ligne, on appelle pgcd avec le diviseur (y) et le reste de la division de x par y *)

print_string "Saisissez valeur x: ";;
let x = read_int();; (*Equivalent à scanf() en C, x vaut la valeur entrée par l'utilisateur. *)

print_string "Saisissez valeur y: ";;
let y = read_int();; (* Idem pour y *)

print_string "PGCD = ";;
print_int (pgcd x y);;
print_newline();;

Suspens....

Saisissez valeur x: 34
Saisissez valeur y: 12
PGCD = 2

On explique ?
pgcd 34 12 = pgcd 12 10............car 34 = 12 * 2 + 10
pgcd 12 10 = pgcd 10 5..............car 12 = 10 * 1 + 2
pgcd 10 5 = 2 **............................**car 10 = 5 * 2 = 0
Cette fonction marche bien ! Essayez la avec d'autres paramètres !

Récursivité Terminale

Cependant, la Récursivité Classique nécessite d'appeler une fonction jusqu'à la condition d'arrêt avant d'agir n'offrant pas une efficacité optimale. Une fonction récursive est dite Terminale lorsque toutes les instructions se font à l'intérieur de la fonction.
Vous allez sans doute vous demander quelle est la différence avec une fonction Récursivité Classique (qu'on appelle aussi non Terminale).

Prenons la fonction factorielle, ceci est sa forme non Terminale que vous connaissez bien maintenant :

let rec factorielle x =
 if x = 1 then 1
 else x * factorielle (x-1);;

Et voici sa version Terminale :

let facto x =
 let rec f x acc = (* Notez l'apparition de la variable acc pour accumulateur *)
  if x = 1 then acc
  else f (x-1) (acc*x) (* acc accumule le résultat jusqu'à ce qu'on le renvoie quand on arrive au cas d'arrêt *)
in f x 1
;; (* Ici on appelle f avec x et acc est fixé à 1 *)

Exemple d'utilisation :

facto 3
- : int 6

facto 4
- : int 24

Dans la version Terminale, il y a x et acc qui varient ! Quand on calcule facto 4, ça revient à faire f x acc avec x = 4 et acc = 1.
facto 4
= f 4 1
= f 3 4 ..............Car 4 * 1 = 4
= f 2 12..............Car 4 * 3 = 12
= f 1 24..............Cas d'arrêt pour x = 1
= 24

Regardez la différence avec la version non récursive pour le même calcul :
facto 4 =
4 * facto (4-1).................Or facto 3 = 3 * facto (3-1)
4 * 3 * facto (3-1).............Or facto 2 = 2 * facto (2-1)
4 * 3 * 2 * facto (2-1).........** Or facto 1 = 1 **
4 * 3 * (2 * 1)
4 * (3 * 2)
(4 * 6)
24

Dans la version non Terminale, pour des valeurs très grande on aura :
x * (x-1) * (x-2) * (x-3) * (x-4) * (x-5) * (x-6) * .... * 5 * 4 * 3 * 2 * 1...qui peut nous conduire à l'erreur Stack Overflow !

C'est-à-dire que la pile d’exécution a atteint sa limite.
La pile d'éxecution est la ligne où l'on fait tous les calculs dans la fonction.
Il y a x facteurs en produits, quand ce x est trop grand on obtient une erreur
Par contre dans la version terminale, il y a exactement 2 données dans la pile !!!
On préfèrera la façon Terminale afin d'éviter de remplir la pile d'exécution.

Toutes les fonctions non Terminales peuvent être écrites en Terminale !
Donc entraînez-vous à réécrire toutes les fonctions récursives de la partie Exercices en Terminale :-O !

Exercices

Codez les fonctions fibonnaci, qui prend en argument un entier x et qui renvoie U_x de la Suite de Fibonnaci, et nb_chiffres, qui prend en argument un entier x et qui renvoie le nombre de chiffre(s) qu'il y a dans x.

fibonnaci 4
3

nb_chiffres 123456
6