Dans un article récent, j’ai choqué pas mal de monde en disant que la récursivité est un concept assez peu utilisé. Je me focalisais sur mon expérience personnelle récente. Il est vrai que ces derniers mois, je n’ai pas eu besoin d’utiliser de fonctions récursives, sans doute car les projets sur lesquels j’ai travaillé ne s’y prêtaient pas.
A vrai dire, la question m’a un peu hanté alors j’ai décidé de faire des recherches et j’ai finalement retrouvé un vieux site où j’avais du utiliser la récursivité pour arriver à mes fins.
Il s’agit d’un problème tout bête sur lequel vous êtes déjà certainement tombé : j’avais un simple système de catégorisation au nombre de sous-niveaux arbitraires (donc, potentiellement infini) et je voulais afficher un sitemap tout ce qu’il y a de plus classique via des listes et sous-listes (tags ul et li).
Ma table category ressemblait à ceci :
+-----------+ | category | +-----------+ | id | | name | | parent_id | +-----------+
idest l’identifiant unique de la catégorienameest le nom de la catégorieparent_idest l’id de la catégorie parente (0 si c’est une catégorie qui se trouve à la racine)
L’algorithme pour afficher mon sitemap est on ne peut plus simple. Je vous épargne volontairement les lignes de code concernant la connexion à la base de données…
<?php
function displaySitemap($n) {
$query = mysql_query("SELECT * FROM category WHERE parent_id = '$n' ORDER BY name");
if (mysql_num_rows($query)) {
echo '<ul>';
while ($category = mysql_fetch_assoc($query)) {
echo '<li><a href="category.php?id='.$category['id'].'">'.$category['name'].'</a>';
displaySitemap($category['id']);
echo '</li>';
}
echo '</ul>';
}
}
displaySitemap(0);
Ce n’est absolument pas la façon la plus propre de procéder mais cela prouve que la récursivité est une notion indispensable et utile !
Mea culpa, donc.
Le blog de Vincent Battaglia 
C’est potentiellement un gouffre à ressources s’il y a beaucoup de récursivité (requêtes imbriquées).
Tu as heureusement un concept plus au point, l’arborescence en arbre : http://dev.mysql.com/tech-resources/articles/hierarchical-data.html
LikeLike
Il manque juste une petite contrainte pour éviter les cycles, bien que j’imagine que celle-ci soit implémentée à la création d’une catégorie (opération nettement moins fréquente que l’affichage) plutôt que là.
LikeLike
AAaaah, la récursivité, ça me rappelle mes cours de programmation avec ce cher Baudoin L. à l’Institut d’info à Namur.
Ne pas oublier le cas terminal 😉
*nostalgie*
LikeLike
Ouais, on est bien d’accord, cet algo est pourri. Déjà rien que mélanger des requêtes SQL avec de l’affichage de code HTML, c’est contre ma religion MVC…
Je voulais juste montrer un cas où la récursivité est utile. C’est clair que je n’ai pas choisi le meilleur algo pour illustrer cela mais ce n’était pas vraiment le but non plus.
@Oncle Tom : Merci pour le tuyau !
LikeLike
Je me souviens à la fin de Matrix 2, quand l’agent arrive dans le vrais monde (par téléphone), je me suis dit: Génial, Zion est une matrice dans la matrice. L’architecte avait parlé de plusieurs Matrice et je les avaient imaginée imbriquées… imaginer vous des Matrices récursives qui feraient à chaque fois croire aux protagonistes qu’ils sont libres, alors qu’ils ne sont que dans une nouvelle sous itération de la matrice!
Bref la suite m’a démontré que les frères (ou soeur?) Wachowski ne sont pas de si brillant geek.
LikeLike
Connaître la récursivité c’est important… surtout pour savoir comment la supprimer dans un algo !
LikeLike
Effectivement la récursivité est utile pour tout un tas de situations. Les situations à base d’arbres en sont le meilleur exemple.
Pour en revenir au post précédent “université et réalité”, les pointeurs sont très utiles également. Premièrement pour comprendre le dessous des choses, deuxièmement parce que le domaine du web est, techniquement, très simple en comparaison à d’autres domaines plus scientifiques où les pointeurs sont utilisés abondamment pour raisons de performance et de contrôle sur le système (entre autres). Dans ma société par exemple, une équipe de personnes bossent quotidiennement en C++ et la maîtrise des pointeurs est donc un pré-requis indispensable.
Autre débat : à l’heure où l’on parle de plus en plus de séparation de couches, de responsabilités, etc j’ai été assez interpellé de voir le code PHP, ce “chaudron” où tout est mélangé : une requête SQL, un foreach avec de l’HTML hardcodé en string, des variables, etc… Sans parler de la syntaxe pas spécialement lisible (underscores, dollars, …). A quand un langage open source digne de ce nom ? Parce que à choisir, je préfère très nettement ASP.NET ou autre
LikeLike
Yves, je suis d’accord avec toi pour ce qui concerne le MVC (voir mon commentaire plus haut).
LikeLike
trop cool, le mea-culpa.
L’exemple, me fait penser à un site d’e-commerce pour le quel j’ai bossé, qui utilisait un module de menu fonctionnant sur ce modèle. Avec 5 catégories de base et parfois jusqu’à 4 sous niveaux, le site faisait plusieurs centaines de requêtes par page, uniquement pour construire son menu! autant vous dire que çà swappait ferme sur le serveur les jours d’affluence…
Quelqu’un a déjà implémenté un algorithme de type “Modified Preorder Tree Traversal” en php/mysql?
Cela semble être une solution assez économique en termes de ressources. Mais j’avoue ne pas avoir bien saisi le concept pour le moment 😉
LikeLike
@Lo.J : effectivement, c’est pas top mais avec un système de cache, ça ne devrait pas poser de problèmes. Par contre, on est bien d’accord que l’algo est crapuleux mais je n’ai toujours pas trouvé de meilleur exemple d’algo récursif UTILE 🙂
LikeLike
Heureusement Mea Culpa lol !
C’est un procédé SUPER utile et SUPER utilisé ! Ça simplifie grandement les choses (même si au départ la notion peut paraître abstraite) et ça optimise souvent grandement le code.
LikeLike
De mémoire, quicksort est un algo récursif (utile)
LikeLike