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をとることがわかります。

ステップバイステップ：

この例では、 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を返します。

再帰の理解の鍵は、メソッドがそれ自身の新しいインスタンスを呼び出すことです。戻り後、呼び出し元インスタンスの実行が続行されます。

再帰を使用してディレクトリツリーを取得する

再帰の使用法の1つは、ファイルシステムのディレクトリツリーのような階層的なデータ構造を、ツリーのレベル数や各レベルのオブジェクト数を知らなくてもナビゲートすることです。この例では、ディレクトリツリー上の再帰を使用して、指定されたディレクトリのすべてのサブディレクトリを検索し、ツリー全体をコンソールに出力する方法を示します。

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) ：

これは実際のディレクトリツリーの印刷を処理する最初の2つの方法です。このメソッドは、ルートディレクトリへのパスを表す文字列をパラメータとして取ります。パスが実際のディレクトリかどうかをチェックし、そうでない場合はDirectoryNotFoundExceptionをスローし、catchブロックで処理されます。パスが実ディレクトリの場合は、パスからDirectoryInfoオブジェクトのrootDirectoryが作成され、2番目のPrintDirectoryTreeメソッドがrootDirectoryオブジェクトでRootLevel 、 RootLevel （値がゼロの整数定数）が呼び出されます。

PrintDirectoryTree(DirectoryInfo, int) ：

この2番目の方法は、作業の正当性を扱います。パラメータとしてDirectoryInfoと整数をとります。 DirectoryInfoは現在のディレクトリで、整数はルートとの相対的なディレクトリの深さです。読みやすいように、出力は現在のディレクトリの深さごとにインデントされているので、出力は次のようになります。

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

現在のディレクトリが印刷されると、そのサブディレクトリが取得され、このメソッドは現在のディレクトリの深さレベルの値よりも1つ多く、呼び出されます。その部分は再帰です：メソッド自体を呼び出します。ツリー内のすべてのディレクトリにアクセスするまで、この方法でプログラムが実行されます。サブディレクトリのないディレクトリに到達すると、メソッドは自動的に戻ります。

このメソッドはUnauthorizedAccessExceptionもキャッチします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

因数計算

数の階乗（！、例えば9！と表示されます）は、その数と1の階乗の乗算です。したがって、例えば、9！ = 9×8！ = 9×8×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 2 = 2×2
• 2 3 = 2×2×2、または2 3 = 2 2×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 };
}