C# Language
Récursivité

Remarques

Décrire récursivement une structure d'objet

La récursivité se produit lorsqu'une méthode s'appelle elle-même. De préférence, il le fera jusqu'à ce qu'une condition spécifique soit remplie, puis il quittera la méthode normalement, pour revenir au point d'où la méthode a été appelée. Si ce n'est pas le cas, une exception de dépassement de capacité de la pile peut se produire en raison d'un trop grand nombre d'appels récursifs.

/// <summary>
/// Create an object structure the code can recursively describe
/// </summary>
public class Root
{
    public string Name { get; set; }
    public ChildOne Child { get; set; }
}
public class ChildOne
{
    public string ChildOneName { get; set; }
    public ChildTwo Child { get; set; }
}
public class ChildTwo
{
    public string ChildTwoName { get; set; }
}
/// <summary>
/// The console application with the recursive function DescribeTypeOfObject
/// </summary>
public class Program
{
    static void Main(string[] args)
    {
        // point A, we call the function with type 'Root'
        DescribeTypeOfObject(typeof(Root));
        Console.WriteLine("Press a key to exit");
        Console.ReadKey();
    }

    static void DescribeTypeOfObject(Type type)
    {
        // get all properties of this type
        Console.WriteLine($"Describing type {type.Name}");
        PropertyInfo[] propertyInfos = type.GetProperties();
        foreach (PropertyInfo pi in propertyInfos)
        {
            Console.WriteLine($"Has property {pi.Name} of type {pi.PropertyType.Name}");
            // is a custom class type? describe it too
            if (pi.PropertyType.IsClass && !pi.PropertyType.FullName.StartsWith("System."))
            {
                // point B, we call the function type this property
                DescribeTypeOfObject(pi.PropertyType);
            }
        }
        // done with all properties
        // we return to the point where we were called
        // point A for the first call
        // point B for all properties of type custom class
    }
}

Récursivité en anglais

La récursion peut être définie comme suit:

Une méthode qui s'appelle jusqu'à ce qu'une condition spécifique soit remplie.

Un exemple simple et excellent de récursivité est une méthode qui obtiendra la factorielle d'un nombre donné:

public int Factorial(int number)
{
    return number == 0 ? 1 : n * Factorial(number - 1);
}

Dans cette méthode, nous pouvons voir que la méthode prendra un argument, number .

Pas à pas:

Prenons l'exemple, exécutant Factorial(4)

1. Est le number (4) == 1 ?
2. Non? retour 4 * Factorial(number-1) (3)
3. Comme la méthode est appelée à nouveau, elle répète maintenant la première étape en utilisant Factorial(3) comme nouvel argument.
4. Cela continue jusqu'à ce que Factorial(1) soit exécuté et que le number (1) == 1 renvoie 1.
5. Globalement, le calcul "se construit" 4 * 3 * 2 * 1 et retourne finalement 24.

La clé pour comprendre la récursivité est que la méthode appelle une nouvelle instance d'elle-même. Après retour, l'exécution de l'instance appelante se poursuit.

Utilisation de la récursivité pour obtenir l'arborescence de répertoires

L'une des utilisations de la récursivité consiste à naviguer dans une structure de données hiérarchique, telle qu'une arborescence de répertoires de systèmes de fichiers, sans connaître le nombre de niveaux de l'arborescence ni le nombre d'objets sur chaque niveau. Dans cet exemple, vous verrez comment utiliser la récursivité dans une arborescence de répertoires pour rechercher tous les sous-répertoires d'un répertoire spécifié et imprimer l'arborescence complète dans la console.

internal class Program
{
    internal const int RootLevel = 0;
    internal const char Tab = '\t';

    internal static void Main()
    {
        Console.WriteLine("Enter the path of the root directory:");
        var rootDirectorypath = Console.ReadLine();

        Console.WriteLine(
            $"Getting directory tree of '{rootDirectorypath}'");

        PrintDirectoryTree(rootDirectorypath);
        Console.WriteLine("Press 'Enter' to quit...");
        Console.ReadLine();
    }

    internal static void PrintDirectoryTree(string rootDirectoryPath)
    {
        try
        {
            if (!Directory.Exists(rootDirectoryPath))
            {
                throw new DirectoryNotFoundException(
                    $"Directory '{rootDirectoryPath}' not found.");
            }

            var rootDirectory = new DirectoryInfo(rootDirectoryPath);
            PrintDirectoryTree(rootDirectory, RootLevel);
        }
        catch (DirectoryNotFoundException e)
        {
            Console.WriteLine(e.Message);
        }
    }

    private static void PrintDirectoryTree(
        DirectoryInfo directory, int currentLevel)
    {
        var indentation = string.Empty;
        for (var i = RootLevel; i < currentLevel; i++)
        {
            indentation += Tab;
        }

        Console.WriteLine($"{indentation}-{directory.Name}");
        var nextLevel = currentLevel + 1;
        try
        {
            foreach (var subDirectory in directory.GetDirectories())
            {
                PrintDirectoryTree(subDirectory, nextLevel);
            }
        }
        catch (UnauthorizedAccessException e)
        {
            Console.WriteLine($"{indentation}-{e.Message}");
        }
    }
}

Ce code est un peu plus compliqué que le strict minimum pour effectuer cette tâche, car il inclut la vérification des exceptions pour gérer les problèmes liés à l'obtention des répertoires. Vous trouverez ci-dessous une ventilation du code en segments plus petits avec des explications sur chacun.

Main :

La méthode principale prend une entrée d'un utilisateur sous forme de chaîne, qui doit être utilisée comme chemin d'accès au répertoire racine. Il appelle ensuite la méthode PrintDirectoryTree avec cette chaîne comme paramètre.

PrintDirectoryTree(string) :

C'est la première des deux méthodes qui gèrent l'impression de l'arborescence de répertoires. Cette méthode prend en paramètre une chaîne représentant le chemin d'accès au répertoire racine. Il vérifie si le chemin est un répertoire réel et, sinon, lève une exception DirectoryNotFoundException qui est ensuite traitée dans le bloc catch. Si le chemin est un répertoire réel, un DirectoryInfo objet rootDirectory est créé à partir du chemin d' accès, et le second PrintDirectoryTree méthode est appelée avec le rootDirectory objet et RootLevel , qui est un nombre entier constant avec une valeur de zéro.

PrintDirectoryTree(DirectoryInfo, int) :

Cette seconde méthode traite le plus gros du travail. Il prend un DirectoryInfo et un entier comme paramètres. DirectoryInfo est le répertoire en cours et l'entier est la profondeur du répertoire par rapport à la racine. Pour faciliter la lecture, la sortie est en retrait pour chaque niveau de profondeur du répertoire en cours, de sorte que la sortie ressemble à ceci:

-Root
    -Child 1
    -Child 2
        -Grandchild 2.1
    -Child 3

Une fois le répertoire en cours imprimé, ses sous-répertoires sont récupérés, et cette méthode est ensuite appelée sur chacun d'eux avec une valeur de niveau de profondeur supérieure au courant. Cette partie est la récursivité: la méthode elle-même. Le programme s'exécutera de cette manière jusqu'à ce qu'il ait visité tous les répertoires de l'arborescence. Lorsqu'il atteint un répertoire sans sous-répertoires, la méthode est automatiquement renvoyée.

Cette méthode intercepte également une UnauthorizedAccessException , qui est lancée si l'un des sous-répertoires du répertoire en cours est protégé par le système. Le message d'erreur est imprimé au niveau d'indentation actuel pour la cohérence.

La méthode ci-dessous propose une approche plus simple de ce problème:

internal static void PrintDirectoryTree(string directoryName)
{
    try
    {
        if (!Directory.Exists(directoryName)) return;
        Console.WriteLine(directoryName);
        foreach (var d in Directory.GetDirectories(directoryName))
        {
            PrintDirectoryTree(d);
        }
    }
    catch (Exception e)
    {
        Console.WriteLine(e.Message);
    }
}

Cela n'inclut pas la vérification d'erreur spécifique ou le formatage de sortie de la première approche, mais cela fait effectivement la même chose. Comme il n'utilise que des chaînes contrairement à DirectoryInfo , il ne peut pas donner accès à d'autres propriétés de répertoire telles que les autorisations.

Séquence de Fibonacci

Vous pouvez calculer un nombre dans la séquence de Fibonacci en utilisant la récursivité.

Suivant la théorie mathématique de F (n) = F (n-2) + F (n-1), pour tout i> 0,

// Returns the i'th Fibonacci number
public int fib(int i) {
    if(i <= 2) {
        // Base case of the recursive function.
        // i is either 1 or 2, whose associated Fibonacci sequence numbers are 1 and 1.
        return 1;
    }
    // Recursive case. Return the sum of the two previous Fibonacci numbers.
    // This works because the definition of the Fibonacci sequence specifies
    // that the sum of two adjacent elements equals the next element.
    return  fib(i - 2) + fib(i - 1);
    
}

fib(10); // Returns 55

Calcul factoriel

La factorielle d'un nombre (noté avec!, Comme par exemple 9!) Est la multiplication de ce nombre par la factorielle de un inférieur. Donc, par exemple, 9! = 9 x 8! = 9 x 8 x 7! = 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1.

Donc, dans le code qui devient, en utilisant la récursivité:

long Factorial(long x)
{
    if (x < 1)
    {
        throw new OutOfRangeException("Factorial can only be used with positive numbers.");
    }

    if (x == 1)
    {
        return 1;
    } else {
        return x * Factorial(x - 1);
    }
}

Calcul PowerOf

Le calcul de la puissance d'un nombre donné peut également se faire de manière récursive. Étant donné un nombre de base n et un exposant e , nous devons nous assurer de diviser le problème en plusieurs parties en diminuant l’exposant e .

Exemple théorique:

• 2² = 2x2
• 2³ = 2x2x2 ou, 2³ = 2² x 2
  C'est là que réside le secret de notre algorithme récursif (voir le code ci-dessous). Il s’agit de prendre le problème et de le séparer en plusieurs parties plus petites et plus simples pour résoudre les problèmes.
• Remarques
  • lorsque le nombre de base est 0, il faut savoir que 0 est 0³ = 0 x 0 x 0
  • quand l'exposant est à 0, il faut être conscient de toujours retourner 1, car c'est une règle mathématique.

Exemple de code:

public int CalcPowerOf(int b, int e) {
    if (b == 0) { return 0; } // when base is 0, it doesn't matter, it will always return 0
    if (e == 0) { return 1; } // math rule, exponent 0 always returns 1
    return b * CalcPowerOf(b, e - 1); // actual recursive logic, where we split the problem, aka: 2³ = 2 * 2² etc..
}

Tests dans xUnit pour vérifier la logique:
Bien que cela ne soit pas nécessaire, il est toujours bon d’écrire des tests pour vérifier votre logique. J'inclus ceux qui sont écrits ici dans le framework xUnit .

    [Theory]
    [MemberData(nameof(PowerOfTestData))]
    public void PowerOfTest(int @base, int exponent, int expected) {
        Assert.Equal(expected, CalcPowerOf(@base, exponent));
    }

    public static IEnumerable<object[]> PowerOfTestData() {
        yield return new object[] { 0, 0, 0 };
        yield return new object[] { 0, 1, 0 };
        yield return new object[] { 2, 0, 1 };
        yield return new object[] { 2, 1, 2 };
        yield return new object[] { 2, 2, 4 };
        yield return new object[] { 5, 2, 25 };
        yield return new object[] { 5, 3, 125 };
        yield return new object[] { 5, 4, 625 };
}