再帰

# 平易な英語での再帰

再帰は次のように定義できます:

特定の条件が満たされるまで自分自身を呼び出すメソッド。

再帰の優れた単純な例は、特定の数値の階乗を取得するメソッドです:

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

このメソッドでは、メソッドが引数 number を取ることがわかります .

ステップバイステップ:

例を考えると、 Factorial(4) を実行します

<オール>
  • number (4) == 1 です ?
  • いいえ? 4 * Factorial(number-1) を返す (3)
  • メソッドがもう一度呼び出されるため、Factorial(3) を使用して最初のステップを繰り返します。 新しい引数として。
  • これは Factorial(1) まで続きます が実行され、number (1) == 1 1 を返します。
  • 全体として、計算は「構築」されます 4 * 3 * 2 * 1 そして最後に 24 を返します。
  • 再帰を理解する鍵は、メソッドが新しいインスタンスを呼び出すことです それ自体の。戻った後、呼び出しインスタンスの実行が続行されます。

    # フィボナッチ数列

    再帰を使用してフィボナッチ数列の数値を計算できます。

    F(n) =F(n-2) + F(n-1) の数学理論に従い、任意の 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
    
    

    # オブジェクト構造を再帰的に記述する

    再帰とは、メソッドが自分自身を呼び出すことです。できれば、特定の条件が満たされるまでそうし、その後、メソッドを正常に終了して、メソッドが呼び出されたポイントに戻ります。そうでない場合、再帰呼び出しが多すぎるためにスタック オーバーフロー例外が発生する可能性があります。

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

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

    再帰の用途の 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 :

    メイン メソッドは、ユーザーからの入力を文字列として受け取ります。これは、ルート ディレクトリへのパスとして使用されます。次に PrintDirectoryTree を呼び出します この文字列をパラメーターとするメソッド。

    PrintDirectoryTree(string) :

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

    PrintDirectoryTree(DirectoryInfo, int) :

    この 2 番目の方法は、作業の矢面に立たされます。 DirectoryInfo かかります パラメータとしての整数。 DirectoryInfo は現在のディレクトリで、整数はルートに対するディレクトリの深さです。読みやすくするために、出力は現在のディレクトリの深さごとにインデントされているため、出力は次のようになります。

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

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

    このメソッドは 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 ではなく文字列のみを使用するため 、権限などの他のディレクトリ プロパティへのアクセスを提供することはできません。

    # PowerOf 計算

    与えられた数のべき乗を計算することも再帰的に行うことができます。底数 n を考える および指数 e 、指数 e を減らして問題をチャンクに分割する必要があります .

    理論上の例:

    • 2² =2x2
    • 2³ =2x2x2または、2³ =2² x 2
      そこに、再帰アルゴリズムの秘密があります (以下のコードを参照)。これは、問題を取り上げて、それをより小さく単純なチャンクに分割して解決することです。
    • メモ
      • 基数が 0 の場合、0³ =0 x 0 x 0 として 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 };
      }
      
      

      # 階乗計算

      数値の階乗 (たとえば 9! のように ! で示される) は、その数値に 1 つ低い階乗を掛けたものです。たとえば、9! =9×8! =9×8×7! =9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 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);
          }
      }
      
      

      # コメント

      再帰を使用すると、各再帰関数呼び出しがスタックに追加されるため、コードに深刻な影響を与える可能性があることに注意してください。呼び出しが多すぎると、StackOverflow が発生する可能性があります 例外。ほとんどの「自然再帰関数」は for として記述できます 、 while または foreach ループ構成で、上品には見えませんが または賢い より効率的になります。

      再帰は常によく考えて慎重に使用してください - 再帰を使用する理由を理解しておいてください:

    • 再帰呼び出しの数が**過剰**でないことがわかっている場合は、再帰を使用する必要があります
        - **過剰**は、使用可能なメモリ量に依存することを意味します
        • ただし、効率が低下する可能性があることに注意してください。たとえば、フィボナッチ再帰では、nth を計算するには シーケンス内の数、計算時間は指数関数的に増加します!

        さらに理論が必要な場合は、以下をお読みください:

        • https://www.cs.umd.edu/class/fall2002/cmsc214/Tutorial/recursion2.html
        • https://en.wikipedia.org/wiki/Recursion#In_computer_science