Récursivité – Initiation avec PHP
Découvrez les principes de base de la programmation récursive en PHP et en quoi cette méthode de programmation vous sera indispensable.
La programmation récursive, par opposition à la méthode itérative, consiste à « remplacer » une boucle (for, while…) par une séquence d’appels de méthodes. Nous pouvons rencontrer la récursivité dans plusieurs scripts comme par exemple le traitement de tableaux où d’objets dont la profondeur est inconnue. Nous allons voir au travers de plusieurs exemples comment la récursivité peut s’intégrer à votre application et vous faire gagner un temps précieux.
01 – La récursivité, qu’est-ce que c’est ?
En programmation, la récursivité consiste à créer une méthode ou une procédure qui s’appelle elle-même. Cela présente des avantages lorsque vous souhaitez effectuer certaines opérations mathématiques ou bien d’autres applications plus concrètes comme par exemple lister l’arborescence d’un répertoire ainsi que tous ses sous-dossiers.
02 – Pourquoi utiliser la récursivité ?
Prenons un exemple concret. Vous souhaitez faire la somme de l’espace occupé sur votre espace Web. Pour cela, vous avez besoin de parcourir chaque répertoire et ses sous-répertoires afin d’additionner la taille de chaque fichier présent. Cependant, vous ignorez la profondeur de chaque arborescence. Dès lors, la méthode récursive va se charger elle-même de « creuser », aussi profonde qu’est votre structure afin de n’omettre aucun fichier. Ceci est bien sûr un exemple simplifié de ce que permet la récursivité. Au cours de votre expérience de développeur, vous serez amené à rencontrer des exemples bien plus complexes.
03 – Les méthodes récursives 1/2
Dans cette étape, nous allons étudier une méthode récursive simple, sans but concret, si ce n’est de comprendre la logique derrière ce type de programmation. Ouvrez un fichier PHP vierge en entrez la méthode suivante en oubliant pas la balise PHP et l’indentation correcte :
function test($nb) {
if($nb > 0) {
$nb--;
echo "Vous avez appelé test($nb)\n";
test($nb);
}
}
Cette méthode accepte un argument que nous allons considérer comme un nombre positif différent de 0 (peu importe sa valeur).
04 – Les méthodes récursives 2/2
Nous allons à présent tester cette fonction en recopiant la ligne ci-dessous :
test(10);
Lorsque vous exécutez le fichier dans votre navigateur, vous devriez voir apparaître le résultat suivant :
Vous avez appelé test(9)
Vous avez appelé test(8)
Vous avez appelé test(7)
Vous avez appelé test(6)
Vous avez appelé test(5)
Vous avez appelé test(4)
Vous avez appelé test(3)
Vous avez appelé test(2)
Vous avez appelé test(1)
Vous avez appelé test(0)
Comme vous pouvez le voir, la méthode a été appelée dix fois, comme nous l’avions demandé au travers du paramètre. Voilà le concept de la récursivité.
05 – Utilisation de données statiques 1/2
Les variables statiques permettent de définir des bases qui seront par la suite remodifiées au cours des récursifs. Si nous reprenons l’exemple étudié dans l’étape précédente, nous pourrions définir $nb = 10; en tant que variable statique dans la méthode.
Ainsi, le code suivant retournera un résultat strictement identique à celui de l’étape précédente.
function test() {
static $nb = 10;
if ($nb > 0) {
$nb--;
echo "Vous avez appelé test($nb)\n";
test();
}
}
06 – Utilisation de données statiques 2/2
Arrêtons-nous un instant sur leur particularité majeure. En effet, nous pourrions considérer que, étant donné que nous déclarons la variable à l’intérieur de la méthode, elle serait réinitialisée à chaque occurrence et nous nous trouverions alors dans une boucle sans fin. Eh bien non ! La variable statique, une fois déclarée, est conservée pendant toutes les phases de la récursivité.
07 – Un exemple basique : une factorielle
Nous allons à présent étudier une méthode récursive qui aura une fonction un peu plus concrète que la précédente. Nous allons établir une factorielle. La factorielle de 5 se note 5! et équivaut à 5! = 5 * 4 * 3 * 2 * 1. Ainsi, nous pouvons en déduire que 5! = 120. Nous allons à présent essayer de trouver cette valeur grâce à la récursivité. Tout d’abord, si nous transposons ceci en équation littérale :
n! = n * (n – 1) * … * 3 * 2 * 1
Ainsi, nous pourrions écrire la méthode suivante qui, de façon récursive, appliquerait l’équation littérale que nous avons écrite ci-dessus :
function fact($n) {
if ($n < 2) {
return 1;
} else {
return $n * facto($n - 1);
}
}
08 - Récupérer l'arborescence d'un dossier
Une des utilisations les plus courantes de la récursivité - et une des plus simples également - consiste à parcourir une arborescence pour en lister le contenu. Nous allons créer une méthode qui va parcourir le premier répertoire et qui, pour chaque élément, va vérifier s'il s'agit d'un sous répertoire. Le cas échéant, elle va appliquer une récursivité afin de parcourir ce sous-répertoire et ainsi de suite. Si l'élément est un fichier, elle le stock dans un tableau (cette méthode va utiliser des fonctions tel que glob() dont je vous invite à prendre connaissance en lisant la documentation de PHP).
function arbo($racine) {
$liste = glob($racine . "/*");
$resultat = array();
foreach ($liste as $element) {
echo "Etude de $element\n";
if (is_dir($element)) {
$resultat = array_merge($resultat, arbo($element));
} else {
array_push($resultat, $element);
}
}
return $resultat;
}
Nous utilisons ici la fonction glob() afin de récupérer le contenu du répertoire courant. Ensuite, pour chaque élément, nous effectuons le test grâce à la fonction is_dir(). Si cette dernière renvoie true, nous appelons à nouveau la fonction, sinon nous ajoutons l'entrée au tableau des résultats.
09 - La récursivité croisée
Nous allons pousser le tutoriel un peu plus loin en voyant la récursivité croisée. Tout d'abord, une petite définition s'impose.
La récursivité croisée fait intervenir non pas une, mais deux méthodes qui s'appellent entre elles. Pour notre exemple, nous allons créer deux méthodes qui vont servir à tester si un nombre est pair ou impair. Bien sûr, dans une contexte de programmation d'applications, ces exemples ne sont peut-être pas les plus optimisés pour effectuer ces actions, mais ils sont très pratiques dans le cadre pédagogique. Nous considérons les deux méthodes suivantes :
function pair($m) {
if ($m == 0) {
return true;
} else {
return impair(m - 1);
}
}
function impair($m) {
if ($m == 0) {
return false;
} else {
return pair($m - 1);
}
}
Voyons plus en détail la séquence qui est effectuée ici. Pour notre premier test, nous souhaitons savoir si 2 est un chiffre pair.
- Nous éxécutons alors la méthode pair(2).
- Nous entrons dans la méthode pair() avec comme argument $m = 2.
- La condition $m == 0 n'est pas validée.
- impair($m - 1) est alors appelée, ce qui nous donne impair(1).
- Nous entrons dans la méthode impair() avec comme argument $m = 1.
- La conditions $m == 0 n'est pas validée.
- pair($m - 1) est alors appelée, ce qui nous donne pair(0).
- Nous entrons dans la méthode pair() avec comme argument $m = 0.
- $m == 0 est validée, la fonction renvoie true.
- 2 est donc chiffre pair.
Cette pratique algorithmique est très peu utilisée mais dans certains cas elle peut s'avérer incontournable.
10 - Les méthodes récursives à plusieurs arguments
Nous avons vu jusqu'à présent des méthodes récursives n'acceptant qu'un seul argument. Cependant, nous pouvons sans problèmes envisager ses méthodes qui requièrent plusieurs arguments.
pour notre exemple, nous allons à nouveau faire appel à nos connaissances mathématiques et nous allons calculer les PGCD (Plus Grand Commun Diviseur). Nous n'allons pas nous lancer dans de longues explications mais le PGCD de deux nombres A et B est le plus grand entier naturel capable de diviser simultanément A et B. Par exemple, le PGCD de 12 et 10 est 2 car 12 = 6 * 2 et 10 = 5 * 2 et que 6 et 2 sont premiers entre eux. Nous allons créer la méthode pgcd() qui acceptera deux paramètres : $a et $b, deux nombres entiers :
function pgcd($a, $b) {
if ($a == 0) {
return $b;
} elseif ($b == 0) {
return $a;
} elseif ($b <= $a) {
return pgcd($a - $b, $b);
} else {
return pgcd($a, $b - $a);
}
}
Ainsi, lorsque nous exécuterons la méthode pgcd(10, 12), après plusieurs exécutions de cette même méthode à l'intérieur d'elle même, nous obtiendrons 2.
11 - Quelques idées de scripts concrets...
Dans vos scripts, il sera très rare que vous deviez calculer des factorielles ou des PGCD. Encore une fois, nous avons utilisé ces exemples dans un but didactique. En revanche, la récursivité pourra être très utilisée pour le listage d'une arborescence (au lieu d'utiliser une boucle while() par exemple), pour traiter un tableau de façon récursive (une forme optimisée de array_map()), et bien d'autres applications.
12 - Conclusion
Au cours de ce tutoriel, nous avons pu découvrir que la récursivité est étroitement liée aux conditions. En effet, une méthode récursive est caractérisée par une condition d'arrêt. Si cette dernière est manquante, nous entrons dans schéma d'une boucle infinie, ce qui causera une erreur. Dès lors, la condition nous sert à vérifier si la condition d'arrêt est remplie. Le cas échéant, nous stoppons la méthode et renvoyons le résultat.