C# Language
Rekurencja

Uwagi

Rekurencyjnie opisz strukturę obiektu

Rekurencja ma miejsce, gdy metoda wywołuje samą siebie. Najlepiej będzie to robić, dopóki nie zostanie spełniony określony warunek, a następnie opuści metodę normalnie, wracając do punktu, z którego metoda została wywołana. Jeśli nie, może wystąpić wyjątek przepełnienia stosu z powodu zbyt wielu wywołań rekurencyjnych.

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

Rekursja zwykłym angielskim

Rekurencję można zdefiniować jako:

Metoda, która wywołuje się do momentu spełnienia określonego warunku.

Doskonały i prosty przykład rekurencji to metoda, która uzyska silnię danej liczby:

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

W tej metodzie możemy zobaczyć, że metoda przyjmuje argument, number .

Krok po kroku:

Biorąc pod uwagę przykład wykonania Factorial(4)

1. Czy number (4) == 1 ?
2. Nie? return 4 * Factorial(number-1) (3)
3. Ponieważ metoda jest wywoływana ponownie, teraz powtarza pierwszy krok, używając Factorial(3) jako nowego argumentu.
4. Factorial(1) do momentu wykonania funkcji Factorial(1) i number (1) == 1 zwraca wartość 1.
5. Ogólnie rzecz biorąc, obliczenie „powiększa” 4 * 3 * 2 * 1 i ostatecznie zwraca 24.

Kluczem do zrozumienia rekurencji jest to, że metoda wywołuje nową instancję samej siebie. Po powrocie wykonywanie instancji wywołującej jest kontynuowane.

Korzystanie z rekurencji w celu uzyskania drzewa katalogów

Jednym z zastosowań rekurencji jest nawigacja w hierarchicznej strukturze danych, takiej jak drzewo katalogów systemu plików, bez wiedzy o tym, ile poziomów ma drzewo ani o liczbie obiektów na każdym poziomie. W tym przykładzie zobaczysz, jak używać rekurencji w drzewie katalogów, aby znaleźć wszystkie podkatalogi określonego katalogu i wydrukować całe drzewo w konsoli.

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

Ten kod jest nieco bardziej skomplikowany niż absolutne minimum do wykonania tego zadania, ponieważ obejmuje sprawdzanie wyjątków w celu obsługi problemów z uzyskaniem katalogów. Poniżej znajduje się podział kodu na mniejsze segmenty wraz z objaśnieniami do każdego z nich.

Main :

Główna metoda pobiera dane wejściowe od użytkownika jako ciąg znaków, który ma służyć jako ścieżka do katalogu głównego. Następnie wywołuje metodę PrintDirectoryTree z tym ciągiem jako parametrem.

PrintDirectoryTree(string) :

Jest to pierwsza z dwóch metod, które obsługują rzeczywiste drukowanie drzewa katalogów. Ta metoda przyjmuje jako parametr ciąg znaków reprezentujący ścieżkę do katalogu głównego. Sprawdza, czy ścieżka jest rzeczywistym katalogiem, a jeśli nie, zgłasza wyjątek DirectoryNotFoundException który jest następnie obsługiwany w bloku catch. Jeśli ścieżka jest prawdziwy katalog, A DirectoryInfo obiekt rootDirectory tworzony jest z drogi, a drugi PrintDirectoryTree metoda jest wywoływana z rootDirectory przedmiotu i RootLevel , która jest stałą liczbą całkowitą o wartości zero.

PrintDirectoryTree(DirectoryInfo, int) :

Ta druga metoda obsługuje ciężar pracy. Pobiera DirectoryInfo i liczbę całkowitą jako parametry. DirectoryInfo to katalog bieżący, a liczba całkowita to głębokość katalogu względem katalogu głównego. Dla ułatwienia odczytu dane wyjściowe są wcięte dla każdego poziomu głęboko w bieżącym katalogu, dzięki czemu dane wyjściowe wyglądają następująco:

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

Po wydrukowaniu bieżącego katalogu pobierane są jego podkatalogi, a następnie wywoływana jest ta metoda dla każdego z nich z wartością poziomu głębi o jedną większą niż bieżąca. Ta część to rekurencja: metoda nazywająca się sama. Program będzie działał w ten sposób, dopóki nie odwiedzi każdego katalogu w drzewie. Gdy osiągnie katalog bez podkatalogów, metoda zwróci się automatycznie.

Ta metoda przechwytuje także wyjątek UnauthorizedAccessException , który jest zgłaszany, jeśli którykolwiek z podkatalogów bieżącego katalogu jest chroniony przez system. Komunikat o błędzie jest drukowany na bieżącym poziomie wcięcia w celu zachowania spójności.

Poniższa metoda zapewnia bardziej podstawowe podejście do tego problemu:

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

Nie obejmuje to konkretnego sprawdzania błędów lub formatowania wyjściowego pierwszego podejścia, ale skutecznie robi to samo. Ponieważ używa tylko ciągów znaków w przeciwieństwie do DirectoryInfo , nie może zapewnić dostępu do innych właściwości katalogu, takich jak uprawnienia.

Ciąg Fibonacciego

Możesz obliczyć liczbę w sekwencji Fibonacciego za pomocą rekurencji.

Zgodnie z matematyczną teorią F (n) = F (n-2) + F (n-1), dla dowolnego 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

Obliczenia czynnikowe

Silnia liczby (oznaczona za pomocą!, Jak na przykład 9!) Jest pomnożeniem tej liczby przez silnię o jeden niższy. Na przykład 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.

Tak więc w kodzie, który staje się za pomocą rekurencji:

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

Obliczanie PowerOf

Obliczenie mocy danej liczby można również wykonać rekurencyjnie. Biorąc pod uwagę liczbę podstawową n i wykładnik e , musimy upewnić się, że problem został podzielony na części, zmniejszając wykładnik e .

Przykład teoretyczny:

• 2² = 2x2
• 2³ = 2x2x2 lub, 2³ = 2² x 2
  W tym tkwi sekret naszego algorytmu rekurencyjnego (patrz poniższy kod). Chodzi o rozwiązanie problemu i podzielenie go na mniejsze i prostsze do rozwiązania fragmenty.
• Notatki
  • gdy numerem bazowym jest 0, musimy pamiętać, aby zwrócić 0 jako 0³ = 0 x 0 x 0
  • kiedy wykładnik wynosi 0, musimy pamiętać, aby zawsze zwracać 1, ponieważ jest to reguła matematyczna.

Przykład kodu:

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

Testy w xUnit w celu weryfikacji logiki:
Chociaż nie jest to konieczne, zawsze warto pisać testy w celu zweryfikowania logiki. Uwzględniam te tutaj napisane w ramach 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 };
}