Editions ENI Livres | Vidéos | e-Formations
La récursivité
Introduction
La récursivité est une notion qui peut être troublante pour des apprentis développeurs. Il s’agit d’un concept qui fait appel à lui-même. On le retrouve dans l’art, avec la mise en abîme, ou dans les mathématiques, au travers des objets fractals. Le sigle ’’pip’’ fait également appel à ce concept, en ce sens qu’il contient le mot ’’pip’’ dans sa forme développée : pip installs packages. Ce qui engendre une mise en abîme de ce genre : pip (pip (pip (pip installs packages) installs packages) installs packages) installs packages… On peut continuer comme ça à l’infini.
Figure géométrique récursive
La récursivité est utilisée lorsqu’un algorithme ou une fonction fait appel ou référence à lui-même. Voyons deux exemples d’algorithmes récursifs connus.
Une factorielle récursive
Pour rappel, la factorielle d’un entier naturel n est une opération mathématique qui demande de multiplier entre eux tous les entiers de 1 à n compris. Par exemple, la factorielle de 5, ou 5! est égale à 1 * 2 *3 * 4 * 5, ce qui peut se décomposer de cette façon :
-
1 * 2 = 2
-
2 * 3 = 6
-
6 * 4 = 24
-
24 * 5 = 120
5! est donc égal à 120.
Passons au pseudo-code :
Algorithme : Factorielle d'un nombre
Fonction factorielle (entier : n)
Variables :
entier : r
Début
r ← 1
Pour i allant de 1 à n avec un pas de 1
r ← r*i
Retourner r
Fin Nous initialisons la variable r à 1. Ensuite, nous bouclons de 1 jusqu’au nombre n, qui est la valeur finale de la factorielle, 5 ici. La boucle Pour fait donc un nombre de tours égal à n, donc 5 dans notre exemple. Lors du premier tour, la valeur initiale de r est 1 et la valeur de l’incrémenteur i pour la boucle Pour est 1, donc l’opération r*i donne 1=*, et 1 * 1 = 1. La valeur 1 écrase l’ancienne valeur de la variable r. Lors du deuxième tour, i vaut 2 (puisque la boucle avance de 1 à 10 avec un pas de 1), r vaut 1, par conséquent le calcul donne 1 * 2 = 2. La valeur 2 remplace la valeur précédente de r. Lors du troisième tour, r vaut 2 et i vaut...
Fibonacci récursif
La suite de Fibonacci, du nom du mathématicien italien Leonardo Fibonacci, est une suite d’entiers naturels dans laquelle chaque terme est le résultat de la somme des deux entiers naturels qui le précèdent. Les dix premiers nombres de Fibonacci (certains font commencer la suite par 0 et d’autres par 1) sont donc : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55
Écrivons l’algorithme de la suite de Fibonacci.
Algorithme : Fibonacci récursif
Fonction suite de Fibonacci(entier : n)
entier : nombre1, nombre2, nombre3
nombre1 ← 0
nombre2 ← 1
Début
Pour i allant de 0 à n-1 avec un pas de 1
nombre3 ← nombre1 + nombre2
nombre1 ← nombre2
nombre2 ← nombre3
Retouner nombre2
Fin L’algorithme retourne la valeur de nombre2, c’est-à-dire la valeur calculée par la suite de Fibonacci.
Que donne cet algorithme pour la valeur 10 ? Commençons au niveau de la boucle Pour. Elle itère de 0 à n-1, c’est-à-dire 9. Elle fait donc 10 tours. Lors du premier tour, le résultat stocké dans nombre3 est 1. Puisque...
