La récursivité est l’un des outils les plus élégants de la programmation : une fonction qui s’appelle elle-même pour résoudre des instances progressivement plus petites d’un problème. Pour parcourir des structures arborescentes — comme le système de fichiers, les arborescences de catégories ou les structures XML — c’est souvent la solution la plus naturelle et efficace. Cet article explique le concept et l’illustre avec un exemple concret en C#.

Comment fonctionne la récursivité

L’idée sous-jacente est simple : une fonction reçoit un nœud comme paramètre, le traite, et s’appelle elle-même autant de fois qu’il y a de branches enfants du nœud courant. Les appels successifs se terminent lorsque les nœuds “feuilles” sont atteints — ceux sans enfants.

Sans une condition de sortie bien définie, la récursivité génère une boucle infinie qui conduit à un stack overflow. La fonction doit donc s’appeler uniquement s’il reste des données à traiter.

Avantages et limites

• Avantage principal : code compact et expressif pour naviguer dans des structures hiérarchiques de profondeur arbitraire.
• Limite 1 : sans gestion correcte de la condition de sortie, elle génère des boucles infinies.
• Limite 2 : chaque appel ajoute un frame à la pile. Sur des structures très profondes, un stack overflow est possible même avec une logique correcte.
• Bonne pratique : minimiser les données passées en paramètres — mieux vaut passer des références ou des indices que copier des objets entiers.

Exemple : Scan récursif du système de fichiers en C#

L’exemple implémente un scan récursif des dossiers du système de fichiers. La fonction ReadFolderFiles reçoit un dossier, le parcourt, et pour chaque sous-dossier trouvé s’appelle elle-même avec le sous-dossier comme nouveau paramètre. L’algorithme se termine lorsqu’il n’y a plus de sous-dossiers à visiter.

using System;
using System.IO;

namespace RecursionOnFS
{
    class Class1
    {
        [STAThread]
        static void Main(string[] args)
        {
            DirectoryInfo d = new DirectoryInfo(@"C:RepertoireDeDepart");
            ReadFolderFiles(d);
        }

        static void ReadFolderFiles(DirectoryInfo pDir)
        {
            DirectoryInfo[] subd = pDir.GetDirectories();
            foreach (DirectoryInfo dd in subd)
            {
                if (dd.Attributes == FileAttributes.Directory)
                {
                    // Appel récursif : descendre dans le sous-dossier
                    ReadFolderFiles(dd);
                }
            }

            FileInfo[] fi = pDir.GetFiles();
            foreach (FileInfo f in fi)
            {
                // Traiter chaque fichier trouvé
                Console.WriteLine(f.FullName);
            }
        }
    }
}

Cet exemple illustre parfaitement le schéma récursif : la condition de sortie est implicite dans la structure de données (quand GetDirectories() retourne un tableau vide, la boucle foreach ne s’exécute pas et la récursivité s’arrête naturellement). Le même pattern s’applique à toute structure arborescente : menus, commentaires imbriqués, catégories hiérarchiques, organigrammes.