C# Language
Herhaling

Opmerkingen

Beschrijf recursief een objectstructuur

Recursie is wanneer een methode zichzelf aanroept. Bij voorkeur zal het dit doen totdat aan een specifieke voorwaarde is voldaan en dan zal het de methode normaal verlaten en terugkeren naar het punt vanwaar de methode werd aangeroepen. Als dit niet het geval is, kan een stack-overflow-uitzondering optreden vanwege te veel recursieve oproepen.

/// <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
    }
}

Recursie in gewoon Engels

Recursie kan worden gedefinieerd als:

Een methode die zichzelf aanroept totdat aan een specifieke voorwaarde is voldaan.

Een uitstekend en eenvoudig voorbeeld van recursie is een methode die de faculteit van een bepaald getal krijgt:

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

In deze methode kunnen we zien dat de methode een argument, number .

Stap voor stap:

Gezien het voorbeeld, het uitvoeren van Factorial(4)

1. Is number (4) == 1 ?
2. Nee? rendement 4 * Factorial(number-1) (3)
3. Omdat de methode nogmaals wordt aangeroepen, herhaalt deze nu de eerste stap met Factorial(3) als het nieuwe argument.
4. Dit gaat door totdat Factorial(1) wordt uitgevoerd en number (1) == 1 retourneert.
5. Over het algemeen "bouwt" 4 * 3 * 2 * 1 en geeft uiteindelijk 24 terug.

De sleutel tot het begrijpen van recursie is dat de methode een nieuw exemplaar van zichzelf aanroept. Na terugkomst gaat de uitvoering van de aanroepende instantie verder.

Recursie gebruiken om directorystructuur te verkrijgen

Een van de toepassingen van recursie is om door een hiërarchische gegevensstructuur te navigeren, zoals een directorystructuur van het bestandssysteem, zonder te weten hoeveel niveaus de boom heeft of het aantal objecten op elk niveau. In dit voorbeeld ziet u hoe u recursie in een mapstructuur kunt gebruiken om alle submappen van een opgegeven map te vinden en de hele boom naar de console af te drukken.

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}");
        }
    }
}

Deze code is iets gecompliceerder dan het absolute minimum om deze taak te voltooien, omdat het uitzonderingscontrole omvat om problemen met het ophalen van de mappen af te handelen. Hieronder vindt u een opsplitsing van de code in kleinere segmenten met uitleg van elk.

Main :

De hoofdmethode neemt een invoer van een gebruiker als een tekenreeks, die moet worden gebruikt als het pad naar de hoofdmap. Vervolgens wordt de methode PrintDirectoryTree met deze tekenreeks als parameter PrintDirectoryTree .

PrintDirectoryTree(string) :

Dit is de eerste van twee methoden die het afdrukken van de mappenlijst verwerken. Deze methode neemt een tekenreeks die het pad naar de hoofdmap vertegenwoordigt als een parameter. Het controleert of het pad een echte map is en, zo niet, gooit een DirectoryNotFoundException die vervolgens wordt verwerkt in het catch-blok. Als het pad een echte map is, wordt een DirectoryInfo object rootDirectory gemaakt op basis van het pad, en wordt de tweede PrintDirectoryTree methode aangeroepen met het rootDirectory object en RootLevel , een geheel getal met een waarde van nul.

PrintDirectoryTree(DirectoryInfo, int) :

Met deze tweede methode wordt het grootste deel van het werk afgehandeld. Het heeft een DirectoryInfo en een geheel getal als parameters nodig. DirectoryInfo is de huidige map en het gehele getal is de diepte van de map ten opzichte van de root. Voor het leesgemak wordt de uitvoer ingesprongen voor elk niveau diep in de huidige map, zodat de uitvoer er als volgt uitziet:

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

Nadat de huidige map is afgedrukt, worden de submappen opgehaald en wordt deze methode vervolgens op elk van de mappen aangeroepen met een dieptewaarde van één meer dan de huidige. Dat deel is de recursie: de methode die zichzelf noemt. Het programma wordt op deze manier uitgevoerd totdat het elke map in de boom heeft bezocht. Wanneer het een map zonder submappen bereikte, keert de methode automatisch terug.

Deze methode vangt ook een UnauthorizedAccessException , die wordt gegenereerd als een van de submappen van de huidige map door het systeem wordt beschermd. De foutmelding wordt afgedrukt op het huidige inspringniveau voor consistentie.

De onderstaande methode biedt een meer eenvoudige benadering van dit probleem:

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);
    }
}

Dit omvat niet de specifieke foutcontrole of uitvoeropmaak van de eerste benadering, maar doet in feite hetzelfde. Omdat het alleen strings gebruikt in tegenstelling tot DirectoryInfo , kan het geen toegang bieden tot andere mapeigenschappen zoals machtigingen.

Fibonacci-reeks

U kunt een getal in de Fibonacci-reeks berekenen met behulp van recursie.

Volgens de wiskundetheorie van F (n) = F (n-2) + F (n-1), voor elke 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

Factorberekening

De faculteit van een getal (aangeduid met!, Zoals bijvoorbeeld 9!) Is de vermenigvuldiging van dat getal met de faculteit van een lagere. Dus bijvoorbeeld 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.

Dus in code wordt dat, met behulp van recursie:

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);
    }
}

PowerOf-berekening

Het berekenen van de kracht van een bepaald nummer kan ook recursief worden gedaan. Gegeven een basisnummer n en exponent e , moeten we ervoor zorgen dat we het probleem in delen splitsen door de exponent e .

Theoretisch voorbeeld:

• 2² = 2x2
• 2³ = 2x2x2 of, 2³ = 2² x 2
  Daarin ligt het geheim van ons recursieve algoritme (zie onderstaande code). Dit gaat over het nemen van het probleem en het opdelen in kleinere en eenvoudiger om brokken op te lossen.
• Notes
  • wanneer het basisnummer 0 is, moeten we er rekening mee houden dat 0 moet worden geretourneerd als 0³ = 0 x 0 x 0
  • wanneer de exponent 0 is, moeten we weten dat we altijd 1 retourneren, omdat dit een wiskundige regel is.

Codevoorbeeld:

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..
}

Test in xUnit om de logica te verifiëren:
Hoewel dit niet nodig is, is het altijd goed om tests te schrijven om je logica te verifiëren. Ik neem deze op die hier zijn geschreven in het xUnit-framework .

    [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 };
}