Du récursif à l'itératif

Un mot sur la récursivité
La récursivité en informatique est un principe qui consiste à définir une routine en fonction d'elle même. Les algorithmes récursifs sont utilisés fréquemment, par exemple pour résoudre un problème de tri, définir une fonction ou une suite mathématique ou encore pour le parcours d'un arbre.

Performances
Bien que la notion de récursivité s'impose naturellement comme solution dans plusieurs problèmes algorithmiques, il est important de réaliser qu'une fois mis en place, un programme récursif chargera la pile à chaque nouvel appel de la routine. Il est alors important d'évaluer la performance d'une telle implémentation en temps, en mémoire et en stabilité.

Dérécursiviser
Si la solution récursive s'avère coûteuse ou instable (débordement de pile), on peut avoir recours à la suppression de la récursivité. Le principe générale de cette suppression consiste à utiliser un algorithme itératif en simulant la pile à l'aide d'une structure de donnée.

Exemple
Le parcours d'un arbre en profondeur consiste à parcourir tous les noeuds d'un arbre en commençant par l'exploration des feuilles à l'extrémité gauche de celui-ci et en remontant par le noeud père. Une mise en oeuvre typique de cette algorithme est le parcours d'un système de fichier.

Dans cette figure, les noeuds sont numérotés dans l'ordre de parcours en profondeur


Algorithme
L'algorithme récursif pour le parcours en profondeur d'un arbre est simple:

fonction parcourir(racine) debut
pour chaque noeud de racine faire
si le noeud n'a pas de fils alors traitement(noeud)
sinon parcourir(noeud)
fin

Le même algorithme en supprimant la récursivité peut s'avérer plus astucieux:

fonction parcourir(racine)
variables
$parcourus <- [racine] debut
empiler(racine)
tant que la pile n'est pas vide faire
$courant <- dépiler()
si $courant pas dans $parcourus alors
traitement($courant)
$parcourus <- $parcourus U courant
tant que $courant a des fils non parcourus faire
$fils <- getFils($courant) si $fils n'a pas de fils alors traitement(fils)
sinon
empiler($courant)
empiler($fils)
sortir de la boucle
fin

Le principe de ce dernier algorithme repose sur l'empilement lorsque au moins un noeud fils existe et de l'arrêt lorsque la pile est vide.

Une implémentation adaptée au problème du parcours d'un système de fichiers écrite en Python peut être téléchargée ici.

Mes nouveaux jouets

Voilà déjà pas mal de temps que je ne poste plus. J'ai commencé un post sur les techniques employées pour la compilation que je n'ai pas terminé. Je compte bien le terminer et le publier un jour ;o)

Quelques problèmes avec mon ordinateur, m'ont coupé de l'Internet. Il faut dire que tout allait bien jusqu'à ce que j'installe xubuntu. En fin de compte, je suis impressionné par cette distribution et charmé par le bureau XFCE.


Peut-être qu'il serait tant de laisser tomber ma Slackware qui est un peu désuète par rapport à l'évolution rapide d'autres distributions?

Mais bon, ce qui m'a retenu le plus ces derniers temps, ceux sont mes nouveaux jouets.

J'ai enfin ma guitare classique.


La finition est parfaite, mais la guitare est déjà bien mal en point, donc pour le moment elle est toujours en réparation. Cette guitare sonne particulièrement bien pour une Vantage (du bas de gamme par Samick). J'en ai un autre modèle à la maison de la même marque, disons une cousine, mais elle sonne mal. J'ai eu bien souvent l'occasion de remarquer que les guitares de même modèles ne sonnent pas forcément de la même manière.

Ca fait des années que je veux ma Cry Baby.


J'ai été gâté encore une fois par ma copine qui me l'a offerte. La 535Q Cry Baby multi-wah est à mon avis LA pédale wha la plus polyvalente que l'on puisse trouver.