[Plan du site]
Vous êtes ici ---
> Le Site du Zér0
> Les tutoriels
> Non-Officiels
> Site Web
> PHP
> Points particuliers
> Lecture du tutoriel
Initiation à la récursivité en PHP : notions, mise en oeuvre et utilisation
Vous vous apprêtez à lire un tutoriel rédigé par un membre de ce site. Malgré tout le soin que ce membre a pu apporter au tutoriel, nous ne pouvons pas garantir que les informations contenues sur cette page sont exactes à 100%. Merci de garder cela en tête lorsque vous lirez cette page ;o)
Bonjour, chers amis Zér0s !
Pour mon second tuto, je vais vous expliquer le concept de récursivité, de fonctions récursives en PHP et vous montrer quelques exemples d'applications. 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 oeuvre ; 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 ce tuto, vous n'aurez pas besoin de connaissances particulières, à part les bases du PHP (sinon, direction les 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
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 :
Code : PHP1
2
3
4
5
6
7
8 | <?php
function Recursive($arg1, $arg2, ...)
{
//Code...
Recursive($arg1 + 2, $arg.$arg, ...);
//Suite du code...
}
?>
|
Vous pouvez voir que dans ce code 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 U
n avec U
0 = 5.
Et U
n+1 = U
n + 5.
Cette suite arithmétique simple nous donne :
U
0 = 5
U
1 = 10
U
2 = 15 ...etc (et donc U
n = 5 + 5n).
On a un exemple ici 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'analyses sur les données des tableaux ou des dossiers.
Si par exemple nous voulons parcourir un tableau, on va utiliser un
foreach. Si ensuite ce tableau contient lui-même un tableau, on peut encore faire 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 multi-dimensionnels) !
Vous devriez maintenant avoir compris ce qu'était que 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 seconde partie du tutoriel, les choses vont se compliquer, car si le principe est plutôt simple, la mise en oeuvre des fonctions récursives est un petit peu plus difficile ...
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 veut mettre
2 à la puissance 2, quatre fois de suite et afficher le résultat. Voici le code :
Code : PHP 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | <?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é" !
), vous devriez comprendre comment ça marche ...
SVP ne me dites pas qu'on aurait pu faire seulement echo ((((2)^2)^2)^2)^2) et que ça aurait donné la même chose... 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.
- Second 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 à la fonction, une copie du code est mise en mémoire !
J'essaye de faire en sorte que vous puissiez comprendre facilement (et ce n'est pas très facile sur ce sujet...), mais si malgré cela vous n'avez pas saisi cet 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 rentrer !
Si vous avez compris cet exemple, nous allons maintenant parler de 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 ?
En effet, pour pouvoir utiliser une variable statique, il faut d'abord la déclarer. On procède de cette manière :
Code : PHP1
2
3
4
5
6
7 | <?php
function MachinRecursif()
{
static $variable_statique = 256;
//Code...
}
?>
|
Vous conviendrez avec moi que ce n'est pas très compliqué !
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 à rebours à partir de 5 avec une fonction récursive !
5... 4... 3... 2... 1... 0... Le code :
Code : PHP 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | <?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 alliez-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 au début, mais dans ce cas, ce serait beaucoup moins drôle pour nous !
Pour résoudre ce problème (qui n'en est pas un en réalité), nous allons avoir recours aux variables statiques !
Code : PHP 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | <?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 ... ???
Et 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 à déjà été déclarée, et si c'est le cas, elle est initialisée avec l'ancienne valeur (dans notre exemple, c'est la valeur décrémentée 4) !
Nos variables conservent donc leurs valeurs après traitement, et ne sont pas
remises à zéro à chaque appel de notre fonction !
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 variables statiques.
Vous connaissez maintenant tout sur la mise en oeuvre 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 oeuvre !
Car c'est bien beau la récursivité, mais si elle n'a pas d'autre utilité que de faire des comptes à rebours, alors c'est très limité... Eh bien non, dans certains cas bien précis, elle se révèle être une arme redoutable (et parfois indispensable) !!!
À travers cette dernière partie, nous allons donc étudier trois cas (et pas crétins, cette fois), où 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 n°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 suffit de taper
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 avec 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 trois petits points 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.
Maintenant voici le code nous permettant de calculer une factorielle grâce à une fonction récursive :
Code : PHP 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | <?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 (auquel cas on arrête 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 n°2: Gestion de contenu - Le 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 le contenu d'un répertoire sur un FTP, avec notre méthode. Ainsi, nous obtiendrons dans un fichier texte le nom et le chemin de tous les fichiers. Notre fichier texte final se présentera de la sorte :
Code : Autre1
2
3
4
5
| /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, concernant cette fonction.
Je vous donne le code :
Code : PHP 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42 | <?php
function listage($path)
{
//On déclare le tableau qui contiendra tous les items 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 le dossier 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))
{
//Ici on fusionne 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 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 copie le tableau dedans
$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étails !
Je ne m'attarderai pas sur les fonctions de traitement des dossiers et des fichiers en PHP, si vous voulez plus d'explications sur ce sujet, rendez-vous sur un tuto voisin
Lire et afficher le contenu d'un dossier !
Voici la manière dont nous procédons.
- 1/- Nous ouvrons le dossier.
- 2/- On cherche la nature de chaque élément se trouvant à l'intérieur (dossier ou fichier).
- 3/- Si c'est un fichier, on l'enregistre dans notre tableau (qui est une variable statique).
- 4/- Sinon c'est un dossier, dans ce cas on fait appel à notre fonction en modifiant la racine afin qu'elle aille lister le contenu de celui-ci (on repart alors au point n°1) ...etc.
- .............
- 5/- Une fois les dossiers parcourus et tous les sous-dossiers épuisés, notre fonction nous 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 n°3: Gestion de données tabulaires - Listage et affichage de tableaux multi-dimensionnels
Dans ce dernier cas, nous allons voir comment traiter un tableau multi-dimensionnel afin d'en afficher les catégories dans une liste HTML.
Voici la structure de notre tableau :
Code : PHP 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36 | <?php
$tb = array( 'Légumes' => array( 'Choux',
'Haricots',
'Epinards'),
'Fruits' => array( 'Agrumes' => array( 'Oranges',
'Clémentines',
'Citrons'),
'Fruits Rouges' => array( 'Cassis',
'Framboises',
'Mûres',
'Groseilles'),
'Autres Fruits' => array( 'Pommes',
'Poires')));
/*
Nous cherchons à afficher ceci :
Légumes :
Choux
Haricots
Epinards
Fruits :
Agrumes :
Oranges
Clémentines
Citrons
Fruits Rouges :
Cassis
Framboises
Mûres
Groseilles
Autres Fruits :
Pommes
Poires
*/
?>
|
Cette fois-ci, vous allez tenter de coder la fonction vous-mêmes. Pour cela, je vais vous donner quelques indices.
- Grâce à foreach, on parcourt le tableau.
- 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 la liste.
Chers amis Zér0s, à vos claviers !
...
....
.....
Pas trop dur ?
.....
....
...
Voici le résultat :
Code : PHP 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35 | <?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',
'Epinards'),
'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 à la coder !
Je ne réexplique pas étant donné que c'est sensiblement la même chose que 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 maintenant être capables de comprendre les scripts récursifs présents sur le net, et aussi être capables 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 faire des analyses comme pour résoudre les Sudokus ou les 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 !
Bon codage !
Tutoriels
Communauté
Mon compte
Recherche
Livre d'or
Publicité
92 Zéros connectés |
7 requêtes |
0.2856s (0.2744s)
