C# Language
재귀

비고

객체 구조를 재귀 적으로 설명합니다.

재귀는 메서드가 자체를 호출 할 때 발생합니다. 특정 조건이 충족 될 때까지 그렇게 할 것이고 메서드가 정상적으로 종료되고 메서드가 호출 된 지점으로 돌아갑니다. 그렇지 않은 경우 너무 많은 재귀 호출로 인해 스택 오버플로 예외가 발생할 수 있습니다.

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

평범한 영어로 재귀

재귀는 다음과 같이 정의 할 수 있습니다.

특정 조건이 충족 될 때까지 자신을 호출하는 메서드입니다.

훌륭하고 간단한 재귀 예제는 주어진 숫자의 계승을 얻을 수있는 방법입니다.

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

이 메소드에서는 메소드가 인수 number 취하는 것을 볼 number 있습니다.

단계별 :

주어진 예를 들어, Factorial(4)

1. number (4) == 1 입니까?
2. 아니? return 4 * Factorial(number-1) (3)
3. 이 메서드는 다시 한 번 호출되기 때문에 Factorial(3) 을 새 인수로 사용하여 첫 번째 단계를 반복합니다.
4. 이것은 Factorial(1) 이 실행될 때까지 계속되며 number (1) == 1 은 1을 반환합니다.
5. 전반적으로 계산은 4 * 3 * 2 * 1 "빌드하고"결국 24를 반환합니다.

재귀를 이해하는 핵심은이 메서드가 새로운 인스턴스 를 호출한다는 것입니다. 리턴 한 후 호출하는 인스턴스의 실행이 계속됩니다.

재귀를 사용하여 디렉토리 트리 가져 오기

재귀를 사용하는 방법 중 하나는 파일 시스템 디렉토리 트리와 같은 계층 적 데이터 구조를 탐색하고 트리의 레벨 수 또는 각 레벨의 객체 수를 모르는 것입니다. 이 예에서는 디렉토리 트리에서 재귀를 사용하여 지정된 디렉토리의 모든 하위 디렉토리를 찾고 콘솔에 전체 트리를 인쇄하는 방법을 보여줍니다.

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

이 코드는 디렉토리 가져 오기와 관련된 문제를 처리하기위한 예외 검사를 포함하기 때문에이 작업을 완료하는 데 최소한의 것보다 다소 복잡합니다. 아래에서 코드의 세부 사항을 각각의 작은 부분으로 찾아 볼 수 있습니다.

Main :

main 메소드는 루트 디렉토리에 대한 경로로 사용되는 문자열로 사용자로부터 입력을받습니다. 그런 다음이 문자열을 매개 변수로 사용하여 PrintDirectoryTree 메서드를 호출합니다.

PrintDirectoryTree(string) :

이것은 실제 디렉토리 트리 인쇄를 처리하는 두 가지 방법 중 첫 번째 방법입니다. 이 메소드는 루트 디렉토리에 대한 경로를 나타내는 문자열을 매개 변수로 사용합니다. 경로가 실제 디렉토리인지 검사하고 그렇지 않은 경우 DirectoryNotFoundException 을 던집니다. 그러면 DirectoryNotFoundException 이 catch 블록에서 처리됩니다. 경로가 실제 디렉토리이면 경로에서 DirectoryInfo 객체 rootDirectory 가 생성되고 두 번째 PrintDirectoryTree 메소드는 rootDirectory 객체와 RootLevel 값이 0 인 정수 상수)을 사용하여 호출됩니다.

PrintDirectoryTree(DirectoryInfo, int) :

이 두 번째 방법은 작업의 정면을 처리합니다. 매개 변수로 DirectoryInfo 와 정수를 사용합니다. DirectoryInfo 는 현재 디렉토리이고, 정수는 루트와 관련된 디렉토리의 깊이입니다. 읽기 쉽게, 출력은 다음과 같이 보이도록 현재 디렉토리의 각 레벨에 대해 들여 쓰기됩니다.

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

현재 디렉토리가 인쇄되면, 그 서브 디렉토리가 검색되고,이 메소드는 각각의 디렉토리에 대해 현재보다 1의 깊이 레벨 값으로 호출됩니다. 그 부분은 재귀입니다 : 그 자체를 호출하는 메소드. 이 프로그램은 트리의 모든 디렉토리를 방문 할 때까지이 방식으로 실행됩니다. 하위 디렉토리가없는 디렉토리에 도달하면 메소드가 자동으로 리턴됩니다.

이 메소드는 또한 현재 디렉토리의 서브 디렉토리 중 하나가 시스템에 의해 보호되는 경우 Throw되는 UnauthorizedAccessException 을 포착합니다. 일관성을 위해 현재 들여 쓰기 수준에서 오류 메시지가 인쇄됩니다.

아래의 방법은이 문제에 대한보다 기본적인 접근 방법을 제공합니다.

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

여기에는 첫 번째 접근 방식의 특정 오류 검사 또는 출력 형식이 포함되지 않지만 실제로는 동일한 작업을 수행합니다. DirectoryInfo 와는 반대로 문자열 만 사용하므로 권한과 같은 다른 디렉토리 속성에 대한 액세스를 제공 할 수 없습니다.

피보나치 서열

재귀를 사용하여 피보나치 수열에서 수를 계산할 수 있습니다.

어떤 i> 0에 대해서 F (n) = F (n-2) + F (n-1)의 수학 이론을 따르면,

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

요인 계산

숫자의 계승표 (예 :!와 같이 표시된!)는 해당 숫자와 1을 곱한 값입니다. 예를 들어, 9! = 9 x 8! = 9 x 8 x 7! = 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1이다.

그래서 재귀를 사용하는 코드에서 :

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 계산

주어진 숫자의 거듭 제곱 계산은 재귀 적으로도 수행 할 수 있습니다. 기본 번호 감안할 때 n 및 지수 e , 우리는 지수의 감소에 의해 덩어리에 문제를 분리해야 할 필요가 e .

이론적 인 예 :

• 2 ² = 2x2
• 2³ = 2x2x2 또는 2³ = 2² x 2
  여기에는 우리의 재귀 알고리즘의 비밀이 있습니다 (아래 코드 참조). 이것은 문제를 취해 그것을 더 작고 더 간단하게 분리하여 청크를 푸는 것에 관한 것입니다.
• 노트
  • 기본 숫자가 0 일 때 0을 0으로 반환해야한다는 것을 알아야합니다. 0 = 0 x 0 x 0
  • 지수가 0 일 때 수학적 규칙이므로 항상 1을 반환해야한다는 것을 알아야합니다.

코드 예제 :

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

xUnit에서 논리를 검증하기위한 테스트 :
이것이 반드시 필요한 것은 아니지만 논리를 검증하기위한 테스트를 작성하는 것이 좋습니다. 여기에는 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 };
}