En mathématique, il arrive souvent qu'un problème soit formulé (ou prouvé) sous forme d'induction (de récurrence).
La récursivité est le mécanisme informatique qui permet de programmer l'induction.
Syntaxiquement, la récursivité ne requiert aucun mot clé supplémentaire. Elle se caractérise simplement
par une méthode qui s'appelle elle-même, on dit "récursivement".
Par exemple, on peut considérer qu'incrémenter 0 fois un compteur est un cas trivial qui consiste à ne rien
faire. Puis incrémenter un compteur n fois, consiste à l'incrémenter 1 fois (on sait faire avec la méthode
incrementer()), puis à l'incrémenter n fois, "récursivement".
1. /** Incrémente 1 fois l'état du compteur */
2. void incrementer() { ... }
3.
4. /** Incrémente l'état nombre fois.
5. * @param nombre doit être ≥ 0 */
6. void incrementer(int nombre) {
7. if (nombre == 0) { // cas limite, nombre == 0
8. // rien à faire
9. } else { // cas général : nombre > 0
10. this.incrementer(); // incrémente 1 fois()
11.
12. // puis appel récursif
13. this.incrementer(nombre - 1);
14. }
15. }
Cette solution a deux intérêts par rapport à la solution précédente.
D'une part, elle ne nécessite pas le traitement du cas limite.
D'autre part, elle ne dépend pas de la façon de compter, elle est commune aux trois compteurs réalisés
jusqu'alors (Compteur, Compteur5Bits
et CompteurNBits).
Il faut cependant faire attention d'identifier clairement un cas limite,
ici nombre nul, et de s'assurer que le programme converge vers ce cas limite,
si nombre est strictement positif, on décrémente de 1 à chaque fois, donc on arrive nécessairement à une
valeur nulle.
Sinon, il est facile d'écrire un programme récursif dont l'exécution ne termine pas.
Remarquons enfin que la surcharge ne cause aucune ambiguïté. L'appel de la ligne 10 n'est pas récursif, il
fait référence à la méthode définie à la ligne 2, pas de paramètre. L'appel de la ligne 13 est récursif, il
fait référence à la méthode définie à partir de la ligne 6, un paramètre entier.
