Initiation à la récursivité en PHP : notions, mise en œuvre et utilisation

Introduction du cours

Bonjour, chers amis Zéros ! :)

Pour mon second tutoriel, je vais vous expliquer le concept de récursivité, des fonctions récursives en PHP et vous montrer quelques exemples d'application. Comme pour mon premier tutoriel sur la librairie xAjax, je ne suis pas parvenu à trouver un cours qui aurait pu m'expliquer de façon claire ce sujet, et c'est ce qui m'a conduit à écrire celui-ci.

Si la récursivité paraît simple pour certains, son approche est très difficile pour d'autres, et tenter de décrypter des codes faisant appel à des fonctions récursives peut se révéler très délicat…

Les fonctions récursives peuvent nous sembler inutiles car la méthode itérative (celle qui consiste à répéter une portion de code grâce à des boucles) est plus simple à comprendre, à relire et à mettre en œuvre ; de plus, nous l'utilisons sans cesse dans nos applications PHP. Pourtant, la méthode récursive est parfois plus avantageuse, surtout lorsqu'il s'agit de parcourir et de travailler sur des données (comme les tableaux par exemple) qui s'étendent à l'infini.

Pour suivre ce tutoriel, vous n'aurez pas besoin de connaissances particulières, à part les bases du PHP (si vous ne les possédez pas, direction le cours de M@teo21) et un peu de concentration pour bien comprendre le principe. Quelques notions de mathématiques seront aussi les bienvenues et pourront vous aider dans l'apprentissage du mécanisme !

Si vous vous sentez prêts, nous allons pouvoir commencer ! ;)

Niveau : 5 / 10 — Intermédiaire.

Notion de récursivité

Bon, crache le morceau ! C'est quoi, une fonction récursive ?

Une fonction récursive est une fonction qui s'appelle elle-même. En PHP, elle se présente de cette façon :

<?php function Recursive($arg1, $arg2, ...) { //Code... Recursive($arg1 + 2, $arg.$arg, ...); //Suite du code... } ?>

Vous pouvez voir dans ce code que la fonction Recursive() s'appelle elle-même, elle va donc être répétée à la manière d'une boucle !

On peut faire une analogie avec les suites mathématiques (si vous ne comprenez pas cet exemple, ne vous y attardez pas).

Exemple

Soit une suite Un avec U0 = 5.
Et Un+1 = Un + 5.
Cette suite arithmétique simple nous donne :
U0 = 5
U1 = 10
U2 = 15… et ainsi de suite (et donc Un = 5 + 5n).

On a ici un exemple d'une fonction mathématique qui s'appelle elle-même. En PHP, c'est la même chose : on appelle notre fonction directement à l'intérieur de celle-ci.

La récursivité va principalement nous servir pour les travaux d'analyse sur des données telles que des tableaux ou des dossiers.
Si par exemple nous voulons parcourir un tableau, nous allons utiliser un foreach. Si ensuite ce tableau contient lui-même un tableau, on peut encore effectuer un foreach imbriqué dans un autre foreach. Le problème se pose lorsqu'on a un nombre indéfini (et infini) de sous-tableaux : dans ce cas, nous sommes alors obligés de faire appel à la récursivité !
Elle va donc nous servir pour l'analyse de données qui s'étendent à l'infini (comme les tableaux multidimensionnels).

Vous devriez maintenant avoir compris ce qu'est la récursivité en PHP. Enfin, je l'espère, car cette première partie du tutoriel est aussi la plus facile : alors si vous n'avez pas compris, on est mal barrés… ^^

Si le concept est clair pour vous, nous allons continuer et passer à la seconde partie ! ;)

Mise en œuvre de la récursivité en PHP, et variables statiques

Dans cette deuxième partie du tutoriel, les choses vont se compliquer ; si le principe est plutôt simple, la mise en œuvre des fonctions récursives est un petit peu plus difficile… :p

Je vais vous donner un exemple concret de ce qu'on peut faire en PHP, et même s'il ne sert à rien, il illustre bien le principe.
Nous allons calculer (((((2)^2)^2)^2)^2), c'est-à-dire qu'on va mettre 2 à la puissance 2, quatre fois de suite, et afficher le résultat. Voici le code :

<?php function puissance($chiffre, $nbre_exposant) { //On vérifie si on doit encore passer le résultat à la puissance $chiffre if($nbre_exposant > 0) { //On appelle notre fonction return puissance($chiffre*$chiffre, $nbre_exposant - 1); } //Sinon on retourne le résultat return $chiffre; } //On définit le chiffre qui sera mis à sa puissance $chiffre = 2; //On choisit le nombre de fois où $chiffre sera mis à sa puissance $nbre_exposant = 4; //On affiche le résultat en faisant appel à notre fonction echo puissance($chiffre, $nbre_exposant); ?>

Avec ce petit exemple (qu'en passant je qualifierais de « bien commenté » :lol: ), vous devriez comprendre comment ça marche…
8

S'il vous plaît, ne me dites pas qu'on aurait simplement pu écrire echo (((((2)^2)^2)^2)^2) et que ça aurait donné le même résultat… Je le sais, c'est juste pour tenter de vous expliquer le principe !

Je vais essayer d'être le plus précis possible dans la description de ce qui se passe.

• Premier appel à la fonction Puissance() : à ce stade, $chiffre = 2 et $nbre_exposant = 4→ comme $nbre_exposant est supérieur à zéro, on refait appel à la fonction en mettant $chiffre au carré et en décrémentant $nbre_exposant.

• Deuxième appel à la fonction Puissance() : à ce stade, $chiffre = 4 et $nbre_exposant = 3→ comme $nbre_exposant est supérieur à zéro, on refait appel à la fonction en mettant $chiffre au carré et en décrémentant $nbre_exposant.

• Troisième appel à la fonction Puissance() : à ce stade, $chiffre = 16 et $nbre_exposant = 2→ comme $nbre_exposant est supérieur à zéro, on refait appel à la fonction en mettant $chiffre au carré et en décrémentant $nbre_exposant.

• Quatrième appel à la fonction Puissance() : à ce stade, $chiffre = 256 et $nbre_exposant = 1→ comme $nbre_exposant est supérieur à zéro, on refait appel à la fonction en mettant $chiffre au carré et en décrémentant $nbre_exposant.

• Cinquième appel à la fonction Puissance() : à ce stade, $chiffre = 65536 et $nbre_exposant = 0→$nbre_exposant est maintenant égal à zéro, on ne rappelle plus la fonction Puissance(), et on retourne $chiffre qui est maintenant égal à 65536 !

Côté serveur, à chaque appel de la fonction, une copie du code est mise en mémoire.

J'essaye de faire en sorte que vous puissiez comprendre facilement (ce qui n'est pas très facile vu le sujet…), mais si malgré cela vous n'avez pas saisi l'exemple, je vous conseille d'imprimer le code sur papier et de reprendre mon explication en l'ayant sous les yeux. Veillez à faire preuve de logique et allez-y pas à pas, ça finira par entrer ! ;)

Si vous avez compris l'exemple, nous allons maintenant parler des variables statiques.
Les variables statiques sont très pratiques dès que l'on se met à travailler avec des fonctions récursives.

Comment déclare-t-on une variable statique ?

Pour pouvoir utiliser une variable statique, il faut d'abord la déclarer. On procède de cette manière :

<?php function MachinRecursif() { static $variable_statique = 256; //Code... } ?>

Vous conviendrez que ce n'est pas très compliqué ! :p

Attention : on ne peut déclarer des variables statiques qu'avec des valeurs qui ne sont pas des expressions !
Par exemple, static $var = 1 + 1; ne fonctionnera pas.

Bon, c'est beau la vie, mais on ne sait toujours pas à quoi sert une variable statique !

Je vais vous expliquer ça avec un nouvel exemple crétin comme je sais si bien les faire.
Le but va être de compter à l'envers en partant de 5 avec une fonction récursive.

5… 4… 3… 2… 1… 0… Le code :

<?php function decollage() { //On définit notre variable à 5 $compteur = 5; //On affiche echo $compteur; //On décrémente $compteur--; if($compteur >= 0) { //On rappelle notre fonction decollage(); } } decollage(); ?>

Et là, c'est le drame ! Internal Error 500 ! Eh oui, ce code ne fonctionne pas.

C'est logique, allez-vous me dire : à chaque fois, la variable $compteur est réinitialisée à 5, on a donc une boucle infinie ; et forcément, le serveur plante !

Alors c'est vrai qu'on pourrait encore se débrouiller autrement en passant un argument à notre fonction comme dans le premier exemple, mais dans ce cas, ce serait beaucoup moins drôle pour nous. :diable:

Pour résoudre ce problème (qui n'en est en réalité pas un), nous allons avoir recours aux variables statiques.

<?php function decollage() { //On définit notre variable à 5 en statique static $compteur = 5; //On affiche echo $compteur; //On décrémente $compteur--; if($compteur >= 0) { //On rappelle notre fonction decollage(); } } decollage(); ?>

Cette fois, ça fonctionne ! ^^

Je ne comprends pas pourquoi ça fonctionne alors que la variable est déclarée à chaque appel à notre fonction…

Voilà tout l'intérêt de nos variables statiques !
À la première déclaration, elles prennent la valeur qu'on a choisie (ici 5), et se comportent dans le reste de notre code comme des variables normales.
Lorsque la fonction est rappelée, à static $compteur = 5;, le serveur vérifie si la variable a déjà été déclarée. Si c'est le cas, il lui assigne l'ancienne valeur (dans notre exemple, c'est la valeur décrémentée, 4).

Nos variables conservent donc leur valeur après traitement, et ne sont pas remises à zéro à chaque appel de notre fonction ! :D

Il y a néanmoins un problème conséquent qu'il faut prendre en compte : une variable statique, une fois déclarée, n'est pas réinitialisée lors d'un nouvel appel à la fonction dans la page. Pour contourner ce problème, on peut détruire la variable grâce à unset. Dans tous les cas, privilégiez toujours la méthode sans variable statique.

Vous connaissez maintenant tout sur la mise en œuvre des fonctions récursives en PHP : fin de la deuxième partie !

Utilisation de la récursivité dans nos codes

Nous voici arrivés au stade final de ce tutoriel, et donc à l'aboutissement de nos nouvelles connaissances que nous allons enfin pouvoir mettre en application !
Car c'est bien beau, la récursivité, mais si ça n'a d'autre utilité que de faire des comptes à rebours, alors c'est très limité… Eh bien non, dans certains cas bien précis, la récursivité se révèle être une arme redoutable (et parfois indispensable) ! :pirate:

Au cours de cette dernière partie, nous allons étudier trois cas (et pas crétins, cette fois) dans lesquels la méthode de la récursivité sera utilisée. Bien sûr, nous définirons pour chaque cas le résultat attendu, nous coderons (euh… je coderai pour vous :-° ), et nous analyserons le code.

Cas no 1 : calcul mathématique récursif — les factorielles

En mathématiques, la récursivité est un outil très pratique.
Je vous propose aujourd'hui le calcul de factorielle : c'est sûrement la fonction récursive la plus connue et aussi la plus codée (il vous suffit de chercher fonction récursive PHP dans Google et vous verrez…), mais elle est loin d'être inutile car il n'existe aucun autre moyen de faire une factorielle en PHP (à part en utilisant la méthode itérative).

Qu'est-ce qu'une factorielle ?

Je reprends la définition de Wikipédia qui me semble simple et claire pour ceux qui ne savent pas ce qu'est une factorielle : la factorielle d'un entier naturel n, notée n!, ce qui se lit soit « factorielle de n » soit « factorielle n », est le produit des nombres entiers strictement positifs inférieurs ou égaux à n.

La factorielle se présente donc de cette façon : n! = n*(n-1)*(n-2)*…*2*1 (les points de suspension illustrent bien la notion d'infini ; et qui dit infini dit récursivité !).

Calculons par exemple la factorielle de 6 : 6! = 6*5*4*3*2*1 = 720.

Voici maintenant le code nous permettant de calculer une factorielle grâce à une fonction récursive :

<?php function factorielle($nbre) { //Si $nbre = 0 on retourne 1 car soit 1! = 1, soit on est arrivés à la fin du calcul if($nbre === 0) { return 1; } else //Sinon on retourne le nombre multiplié par le reste de sa factorielle (avec $nbre décrémenté) { return $nbre*factorielle($nbre-1); } } //On affiche la factorielle de 6 echo factorielle(6); ?>

Bon, ce n'est pas très difficile à comprendre : à chaque appel de fonction, on vérifie si $nbre n'est pas égal à 0. Si c'est le cas, on stoppe l'exécution de la fonction, sinon on multiplie $nbre par le résultat de la fonction factorielle (qui est donc rappelée) en décrémentant $nbre.

Cas no 2 : gestion de contenu — listage de dossiers

Le simple listage d'un dossier ne requiert pas de fonction récursive, mais lorsqu'il s'agit de lister le contenu d'un dossier, contenant un sous-dossier, qui contient lui-même un sous-dossier, et de parcourir toute une arborescence, la méthode récursive s'impose. Nous allons donc essayer de lister avec notre méthode le contenu d'un répertoire sur un FTP. Nous obtiendrons ainsi dans un fichier texte le nom et le chemin de tous les fichiers. Notre fichier texte final se présentera de la sorte :

/index.php /image/img1.jpg /image/small_img/img2.jpg /image/small_img/img3.jpg /image/large_img/img4.jpg

Merci à bluestorm pour son aide à propos de cette fonction. ;)
Je vous donne le code :

<?php function listage($path) { //On déclare le tableau qui contiendra tous les éléments de nos dossiers $tableau_elements = array(); //On ouvre le dossier $dir = opendir($path); //Pour chaque élément du dossier... while (($element_dossier = readdir($dir)) !== FALSE) { //Si l'élément est lui-même un dossier (en excluant les dossiers parent et actuel), on appelle la fonction de listage en modifiant la racine du dossier à ouvrir if ($element_dossier != '.' && $element_dossier != '..' && is_dir($path.'/'.$element_dossier)) { //On fusionne ici le tableau grâce à la fonction array_merge. Au final, tous les résultats de nos appels récursifs à la fonction listage fusionneront dans le même tableau $tableau_elements = array_merge($tableau_elements, listage($path.'/'.$element_dossier)); } elseif ($element_dossier != '.' && $element_dossier != '..') { //Sinon, l'élément est un fichier : on l'enregistre dans le tableau $tableau_elements[] = $path.'/'.$element_dossier; } } //On ferme le dossier closedir($dir); //On retourne le tableau return $tableau_elements; } //On définit la racine...