C# Language
Rekursion

Anmärkningar

Beskriv rekursivt en objektstruktur

Rekursion är när en metod kallar sig själv. Det kommer företrädesvis att göra det tills ett specifikt villkor är uppfyllda och sedan kommer det att lämna metoden normalt och återgå till den punkt från vilken metoden kallades. Om inte, kan ett undantag från stacköversvämningar uppstå på grund av för många rekursiva samtal.

/// <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 på vanligt engelska

Rekursion kan definieras som:

En metod som kallar sig själv tills ett specifikt villkor är uppfylld.

Ett utmärkt och enkelt exempel på rekursion är en metod som får faktorn för ett visst antal:

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

I den här metoden kan vi se att metoden tar ett argument, number .

Steg för steg:

Med exemplet, utförande av Factorial(4)

1. Är number (4) == 1 ?
2. Nej? retur 4 * Factorial(number-1) (3)
3. Eftersom metoden kallas igen, upprepar den nu det första steget med Factorial(3) som det nya argumentet.
4. Detta fortsätter tills Factorial(1) körs och number (1) == 1 returnerar 1.
5. Sammantaget beräkningen "bygger upp" 4 * 3 * 2 * 1 och returnerar slutligen 24.

Nyckeln till att förstå rekursion är att metoden kallar en ny instans av sig själv. Efter att ha återvänt fortsätter exekveringen av den anropande instansen.

Använda rekursion för att få katalogträd

En av användningarna av rekursion är att navigera genom en hierarkisk datastruktur, som ett filsystemkatalogträd, utan att veta hur många nivåer trädet har eller antalet objekt på varje nivå. I det här exemplet ser du hur du använder rekursion i ett katalogträd för att hitta alla underkataloger i en specificerad katalog och skriva ut hela trädet till konsolen.

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

Den här koden är något mer komplicerad än det absoluta minimumet för att slutföra denna uppgift, eftersom den inkluderar undantagskontroll för att hantera eventuella problem med att få katalogerna. Nedan hittar du en uppdelning av koden i mindre segment med förklaringar av var och en.

Main :

Huvudmetoden tar en inmatning från en användare som en sträng, som ska användas som sökväg till rotkatalogen. Den kallar sedan PrintDirectoryTree metoden med denna sträng som parameter.

PrintDirectoryTree(string) :

Detta är den första av två metoder som hanterar den verkliga katalogträdutskriften. Den här metoden tar en sträng som representerar sökvägen till rotkatalogen som en parameter. Den kontrollerar om sökvägen är en verklig katalog, och om inte, kastar en DirectoryNotFoundException som sedan hanteras i fångstblocket. Om sökvägen är en riktig katalog skapas ett DirectoryInfo objekt rootDirectory från sökvägen, och den andra PrintDirectoryTree metoden kallas med rootDirectory objektet och RootLevel , som är en heltalskonstant med ett värde på noll.

PrintDirectoryTree(DirectoryInfo, int) :

Denna andra metod hanterar arbetet. Det tar ett DirectoryInfo och ett heltal som parametrar. DirectoryInfo är den aktuella katalogen och heltalet är katalogets djup relativt roten. För att underlätta läsningen indikeras utgången för varje nivå djupt som den nuvarande katalogen är, så att utgången ser ut så här:

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

När den nuvarande katalogen har skrivits ut hämtas dess underkataloger, och denna metod kallas sedan på var och en av dem med ett djupnivåvärde på mer än den nuvarande. Den delen är rekursionen: metoden som kallar sig själv. Programmet körs på detta sätt tills det har besökt varje katalog i trädet. När den nådde en katalog utan underkataloger kommer metoden att återgå automatiskt.

Denna metod fångar också en UnauthorizedAccessException som kastas om någon av underkatalogerna i den aktuella katalogen är skyddade av systemet. Felmeddelandet skrivs ut på den aktuella indragningsnivån för konsistens.

Metoden nedan ger en mer grundläggande strategi för detta 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);
    }
}

Detta inkluderar inte den specifika felkontrollen eller utdataformateringen av den första metoden, men det gör faktiskt samma sak. Eftersom den bara använder strängar i motsats till DirectoryInfo , kan den inte ge åtkomst till andra katalogegenskaper som behörigheter.

Fibonacci-sekvens

Du kan beräkna ett tal i Fibonacci-sekvensen med rekursion.

Följer matteorin om F (n) = F (n-2) + F (n-1), för alla 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

Faktoriell beräkning

Faktoriet för ett nummer (betecknat med!, Som till exempel 9!) Är multiplikationen av det numret med faktoriet till ett lägre. Så till exempel 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.

Så i kod som blir, med 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 beräkning

Beräkning av kraften hos ett givet antal kan också göras rekursivt. Med ett basnummer n och exponent e måste vi se till att dela problemet i bitar genom att minska exponenten e .

Teoretiskt exempel:

• 2² = 2x2
• 2³ = 2x2x2 eller, 2³ = 2² x 2
  Där ligger hemligheten med vår rekursiva algoritm (se koden nedan). Det handlar om att ta problemet och separera det i mindre och enklare att lösa bitar.
• anteckningar
  • när basnumret är 0, måste vi vara medvetna om att returnera 0 som 0³ = 0 x 0 x 0
  • när exponenten är 0 måste vi vara medvetna om att alltid returnera 1, eftersom det här är en matematisk regel.

Kodsexempel:

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

Testar i xUnit för att verifiera logiken:
Även om detta inte är nödvändigt, är det alltid bra att skriva tester för att verifiera din logik. Jag inkluderar de här som är skrivna i xUnit-ramverket .

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