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 ! ;)
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 ! ;)
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
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 :
Vous conviendrez que ce n'est pas très compliqué ! :p
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.
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();
?>
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 !
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 :
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
$path = '.';
//Appel à notre fonction
$tableau_elements = Listage($path);
//On ouvre un fichier et on y copie le tableau
$file = fopen('./arborescence.txt', 'w+');
fwrite($file, implode($tableau_elements, "\n"));
fclose($file);
?>
Comment ce code de vingt-cinq lignes s'y prend-il pour lister le contenu de nos répertoires ?
Comme d'habitude, il faut examiner le problème pas à pas. Et comme c'est légèrement plus compliqué que dans le cas précédent, je vais vous expliquer cela en détail. Je ne m'attarderai pas sur les fonctions de traitement des dossiers et des fichiers en PHP. Si vous voulez plus d'explications à ce sujet, rendez-vous dans un tutoriel voisin : lire et afficher le contenu d'un dossier !
Voici la manière dont nous procédons.
On ouvre le dossier.
On détermine la nature de chaque élément se trouvant à l'intérieur (dossier ou fichier).
Si c'est un fichier, on l'enregistre dans notre tableau (qui est une variable statique).
Si c'est un dossier, on fait appel à notre fonction en modifiant la racine afin qu'elle aille lister le contenu de celui-ci (on repart alors au point no 1), etc.
Une fois tous les dossiers parcourus, notre fonction retourne le tableau contenant tous les éléments de notre FTP. Nous n'avons plus qu'à l'enregistrer dans un fichier (ici arborescence.txt).
Voilà, c'est une boucle ; ainsi, tant que notre fonction trouvera des sous-dossiers, elle ira les explorer, permettant ainsi de parcourir toute l'arborescence de notre FTP !
Cas no 3 : gestion de données tabulaires — listage et affichage de tableaux multidimensionnels
Dans ce dernier cas, nous allons voir comment traiter un tableau multidimensionnel afin d'en afficher toutes les entrées hiérarchiquement dans une liste HTML. Voici la structure de notre tableau :
Cette fois-ci, vous allez tenter de coder la fonction vous-mêmes. Pour cela, je vais vous donner quelques indices :
on parcourt le tableau grâce à foreach ;
on vérifie si on est en présence d'un tableau avec is_array($value) ;
si c'est un tableau, on réitère la fonction, sinon on ajoute $value à la liste.
Chers amis Zéros, à vos claviers !
...
....
.....
Pas trop dur ?
.....
....
...
Voici la correction :
<?php
function ListageArray($tb)
{
//Pour chaque élément du tableau...
foreach($tb as $key => $value)
{
//Si l'élément est un tableau, on appelle la fonction pour qu'elle le parcoure
if(is_array($value))
{
echo $key.' :<ul>';
ListageArray($value);
echo '</ul><br />';
}
else //Sinon, c'est un élément à afficher, alors on le liste !
{
echo '<li>'.$value.'</li>';
}
}
}
$tb = array( 'Légumes' => array( 'Choux',
'Haricots',
'Épinards'),
'Fruits' => array( 'Agrumes' => array( 'Oranges',
'Clémentines',
'Citrons'),
'Fruits rouges' => array( 'Cassis',
'Framboises',
'Mûres',
'Groseilles'),
'Autres fruits' => array( 'Pommes',
'Poires')));
ListageArray($tb);
?>
J'espère que vous aviez réussi à coder cette fonction ! Je ne réexplique pas étant donné que c'est sensiblement la même chose que pour le listage de dossiers. :)
Ce tutoriel est maintenant terminé !
N'ayant pas réussi à trouver de bonnes questions à vous poser, j'ai préféré m'abstenir plutôt que de vous servir un QCM sans intérêt.
Avec ces bases, vous devriez être capables de comprendre les scripts contenant des fonctions récursives présents sur le Net, et également d'en élaborer quelques-uns. ^^
On ne se rend pas compte du nombre de codes pouvant faire appel à des fonctions récursives ; je pense notamment aux moteurs de templates, aux opérations sur les dossiers, ou encore pour effectuer des analyses comme la résolution de Sudokus ou de labyrinthes (cf. concours)… Il ne vous reste maintenant plus qu'à bosser un peu pour écrire de belles fonctions !
Ce tutoriel n'avait pas pour vocation de vous apprendre tout sur tout à propos de la récursivité, ce n'est bien sûr qu'une initiation. Mais j'espère qu'il vous aura enseigné quelque chose d'utile, et si c'est le cas, vous m'en verrez très satisfait ! Je vous invite donc à laisser vos commentaires et une note pour que je puisse connaître vos impressions. ;)