C# Language
Rekursion

Bemerkungen

Rekursiv eine Objektstruktur beschreiben

Rekursion ist, wenn eine Methode sich selbst aufruft. Vorzugsweise tut dies so lange, bis eine bestimmte Bedingung erfüllt ist, und dann wird die Methode normal beendet, und es wird zu dem Punkt zurückgekehrt, von dem aus die Methode aufgerufen wurde. Wenn nicht, kann eine Stapelüberlaufausnahme aufgrund zu vieler rekursiver Aufrufe auftreten.

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

Rekursion im Klartext

Rekursion kann definiert werden als:

Eine Methode, die sich selbst aufruft, bis eine bestimmte Bedingung erfüllt ist.

Ein hervorragendes und einfaches Beispiel für eine Rekursion ist eine Methode, die die Fakultät einer gegebenen Zahl erhält:

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

In dieser Methode können wir sehen, dass die Methode ein Argument, number .

Schritt für Schritt:

In diesem Beispiel wird Factorial(4)

1. Ist die number (4) == 1 ?
2. Nein? Rückkehr 4 * Factorial(number-1) (3)
3. Da die Methode erneut aufgerufen wird, wiederholt sie nun den ersten Schritt mit Factorial(3) als neuem Argument.
4. Dies setzt sich fort, bis Factorial(1) ausgeführt wird und number (1) == 1 zurückgibt.
5. Insgesamt "baut" die Berechnung 4 * 3 * 2 * 1 und gibt schließlich 24 zurück.

Der Schlüssel zum Verständnis der Rekursion ist, dass die Methode eine neue Instanz von sich selbst aufruft. Nach der Rückkehr wird die Ausführung der aufrufenden Instanz fortgesetzt.

Verwenden der Rekursion zum Abrufen der Verzeichnisstruktur

Eine der Anwendungen der Rekursion ist das Navigieren durch eine hierarchische Datenstruktur, wie z. B. eine Dateisystemverzeichnisstruktur, ohne zu wissen, wie viele Ebenen die Baumstruktur hat oder wie viele Objekte auf jeder Ebene vorhanden sind. In diesem Beispiel erfahren Sie, wie Sie Rekursion für eine Verzeichnisstruktur verwenden, um alle Unterverzeichnisse eines angegebenen Verzeichnisses zu finden und die gesamte Struktur auf der Konsole zu drucken.

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

Dieser Code ist etwas komplizierter als das Nötigste, um diese Aufgabe auszuführen, da er die Ausnahmebestimmung beinhaltet, um Probleme beim Abrufen der Verzeichnisse zu behandeln. Nachfolgend finden Sie eine Aufschlüsselung des Codes in kleinere Segmente mit Erläuterungen.

Main :

Die Hauptmethode nimmt eine Eingabe von einem Benutzer als Zeichenfolge an, die als Pfad zum Stammverzeichnis verwendet werden soll. Dann ruft sie die PrintDirectoryTree Methode mit dieser Zeichenfolge als Parameter auf.

PrintDirectoryTree(string) :

Dies ist die erste von zwei Methoden, die den tatsächlichen Verzeichnisbaumdruck verarbeiten. Diese Methode verwendet einen String, der den Pfad zum Stammverzeichnis als Parameter darstellt. Es wird geprüft, ob der Pfad ein tatsächliches Verzeichnis ist, und wenn nicht, wird eine DirectoryNotFoundException ausgelöst, die dann im catch-Block behandelt wird. Wenn der Pfad ein reales Verzeichnis ist, wird aus dem Pfad ein DirectoryInfo Objekt rootDirectory erstellt, und die zweite PrintDirectoryTree Methode wird mit dem rootDirectory Objekt und mit RootLevel rootDirectory RootLevel handelt es sich um eine Ganzzahlkonstante mit dem Wert null.

PrintDirectoryTree(DirectoryInfo, int) :

Diese zweite Methode übernimmt die Hauptlast der Arbeit. Als Parameter werden eine DirectoryInfo und eine Ganzzahl verwendet. DirectoryInfo ist das aktuelle Verzeichnis und die Ganzzahl ist die Tiefe des Verzeichnisses relativ zum Stamm. Um das Lesen zu erleichtern, ist die Ausgabe für jede Ebene tief im aktuellen Verzeichnis eingerückt, sodass die Ausgabe folgendermaßen aussieht:

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

Sobald das aktuelle Verzeichnis gedruckt ist, werden seine Unterverzeichnisse abgerufen, und diese Methode wird dann für jedes Verzeichnis mit einem Tiefenwert von mehr als dem aktuellen aufgerufen. Dieser Teil ist die Rekursion: die Methode, die sich selbst aufruft. Das Programm wird auf diese Weise ausgeführt, bis jedes Verzeichnis in der Baumstruktur aufgerufen wurde. Wenn ein Verzeichnis ohne Unterverzeichnisse erreicht wurde, wird die Methode automatisch zurückgegeben.

Diese Methode fängt auch eine UnauthorizedAccessException , die ausgelöst wird, wenn eines der Unterverzeichnisse des aktuellen Verzeichnisses vom System geschützt wird. Die Fehlermeldung wird aus Konsistenzgründen auf der aktuellen Einrückungsebene gedruckt.

Die folgende Methode bietet einen grundlegenderen Ansatz für dieses Problem:

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

Dies schließt nicht die spezifische Fehlerprüfung oder Ausgabeformatierung des ersten Ansatzes ein, sondern führt tatsächlich dasselbe aus. Da es im Gegensatz zu DirectoryInfo nur Zeichenfolgen verwendet, kann es keinen Zugriff auf andere Verzeichniseigenschaften wie Berechtigungen gewähren.

Fibonacci-Folge

Sie können eine Zahl in der Fibonacci-Sequenz durch Rekursion berechnen.

Nach der mathematischen Theorie von F (n) = F (n-2) + F (n-1) für jedes 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

Fakultätsberechnung

Die Fakultät einer Zahl (mit!, Wie zum Beispiel 9!) Ist die Multiplikation dieser Zahl mit der Fakultät Eins. Also zum Beispiel 9! = 9 x 8! = 9 x 8 x 7! = 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1.

Also im Code wird das mit Rekursion:

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-Berechnung

Die Berechnung der Potenz einer gegebenen Zahl kann auch rekursiv erfolgen. Bei einer Basisnummer n und einem Exponenten e müssen wir sicherstellen, dass das Problem in Chunks aufgeteilt wird, indem der Exponent e verringert wird.

Theoretisches Beispiel:

• 2² = 2x2
• 2³ = 2 · 2 · 2 oder 2³ = 2² · 2
  Darin liegt das Geheimnis unseres rekursiven Algorithmus (siehe den Code unten). Hier geht es darum, das Problem in kleinere und einfacher zu lösende Brocken aufzulösen.
• Anmerkungen
  • Wenn die Basisnummer 0 ist, müssen wir uns bewusst machen, 0 als 0³ = 0 x 0 x 0 zurückzugeben
  • Wenn der Exponent 0 ist, müssen wir uns bewusst sein, immer 1 zurückzugeben, da dies eine mathematische Regel ist.

Code-Beispiel:

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 in xUnit zur Überprüfung der Logik:
Obwohl dies nicht notwendig ist, sollten Sie immer Tests schreiben, um Ihre Logik zu überprüfen. Ich füge die hier im xUnit-Framework geschriebenen ein .

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